[프로그래머스] 땅따먹기

dp인 걸 눈치챘으나, 처음에 점화식을 못썼다

dp[x][y]: land[x][y]를 선택할 때, 누적합의 최댓값
land[x][y]를 선택하면, 그 전 row에서 dp[x-1][y]를 제외한dp[x-1][j]중에서 최댓값을 고르면 된다.

정답은 마지막 row의 최댓값이다.(max(dp[-1]))

시간복잡도는 $O(4n)=O(n)$이다.

def solution(land):
    answer = 0
    N = len(land)
    dp = [[0 for _ in range(4)] for _ in range(N)]
    for j in range(4):
        dp[0][j] = land[0][j]
        
    for i in range(1, N):
        for j in range(4):
            dp[i][j] = land[i][j]
            
            # select max value of dp[i - 1][j]
            max_value = 0 # 0 < land[i][j] <= 100
            for k in range(4):
                if k != j:
                    max_value = max(max_value, dp[i - 1][k])
            dp[i][j] += max_value
    
    answer = max(dp[-1])
    return answer