프로그래머스 level 2 - 땅따먹기

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

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

 

완전탐색하면 당연히 시간 초과 나고

한 행 씩 내려갈 수록 값은 커지며, 그 전 행의 값들 중 같은 열이 아니면서 가장 큰 값을 더한 값만 계산하며 배열의 값을 갱신해주면 된다.

 

예시>

[[1,2,3,5],[5,6,7,8],[4,3,2,1]]

1	2	3	5
10 (5 + 5)	11 (5 + 6)	12 (5 + 7)	11 (3 + 8)
16 (12 + 4)	15 (12 + 3)	13 (11 + 2)	13 (12 + 1)

def solution(land):
    for i in range(1, len(land)):
        land[i][0] += max(land[i-1][1], land[i-1][2], land[i-1][3])
        land[i][1] += max(land[i-1][0], land[i-1][2], land[i-1][3])
        land[i][2] += max(land[i-1][0], land[i-1][1], land[i-1][3])
        land[i][3] += max(land[i-1][0], land[i-1][1], land[i-1][2])
        
    # print(land[-1]) # [16, 15, 13, 13]
    return max(land[-1])