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

문제

문제

그리디를 활용하여 해결하면, 시간 초과가 발생하는 문제입니다.
따라서, dp를 활용하여 최적의 결과가 보장되도록 구현해주어야 합니다.

Python

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])

    return max(land[len(land)-1])

문제 조건 중 연속된 열을 지나갈 수 없으므로, 각 열에서 윗 열을 제외하고 최댓값이 구해지도록 위와 같이 구현해줍니다.
마지막 행에서 최댓값을 구해주어야 하므로, max(land[len(land)-1])과 같이 구현해 줍니다.