땅따먹기 파이썬 (프로그래머스)

문제 설명은 아래 링크를 통해서

https://programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

 

풀이방법

n번째 행에 있는 4가지 점수들 입장에서 생각해보자

(15)점수가 선택될 경우는 1번행의 1,3,4번째 점수를 밟고 넘어온 경우다.

다른 점수들도 마찬가지로 이전 점수들 중에서 자신의 열을 제외한 나머지 점수들 중에서 가장 큰 점수를 가진 점수를 선택하면 자신이 선택된 경우의 수에서 가장 큰 점수를 얻을 수 있게 되는 것이다.

 

이전 행이 만약 여태 건너온 점수들의 합산을 나타낸다면 제일 마지막 행의 점수는 자신이 선택된 경우 가장 큰 점수를 나타내게 된다.

 

두번째 행은 첫번째 행에서 자신 열에 위치한 점수를 제외한 나머지 점수 중에서 가장 큰 값을 선택하여 자신과 더한다.

이렇게 행이 누적되는 식으로 점수를 더하고 마지막 행에서 가장 큰 값을 선택하면 정답이 된다.

def solution(land):
    for i in range(1,len(land)):
        for j in range(len(land[i])):
            land[i][j]+=max(land[i-1][:j]+land[i-1][j+1:])
    
    
    #확인용
    for i in land:
        print(i)
        
    
    return max(land[-1])

 

느낀점

1.나 설명 진짜 못한다.......

2.다른 사람 코드를 봤는데 놀랄만큼 똑같더라....

  BFS, DFS등 알고는 있지만 코테를 위해 각잡고 공부하지 않아서 오히려 단순히 문제 접근을 하다보니 답을 찾았다.