[프로그래머스] 땅따먹기 문제 풀이

1. 문제

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

2. 풀이

dp 를 이용해서 문제를 해결합니다. 현재 위치로 올 수 있는 경로까지의 값 중에서 가장 큰 값과 현재의 값을 더하는 식을 반복합니다.

def solution(land):
    dp = [[0]*4 for i in range(len(land))]

    for i, x in enumerate(land[0]):
        dp[0][i] = land[0][i]

    for i in range(1, len(land)):
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]) + land[i][0]
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2], dp[i - 1][3]) + land[i][1]
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][3]) + land[i][2]
        dp[i][3] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + land[i][3]

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

PREVIOUS[프로그래머스] 야근 지수 문제 풀이

NEXT[프로그래머스] 문자열 내림차순으로 배치하기 문제 풀이