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

문제 보기

 

[사용한 알고리즘]

DP(동적 프로그래밍)

 

[문제 접근]

현재 위치의 최고점은 현재 위치 - 1 행의 다른 열 중 최댓값과 현재 위치의 칸의 값을 합치면 됩니다.  

 

[알고리즘]

1. dp 배열 첫 행에 입력받은 land 첫 행 값을 대입합니다.

2. 1행부터 위에서 언급한 문제 접근 방식을 구현합니다.

3. 마지막행까지 2번 과정을 수행한 후 마지막행의 최고점을 출력합니다.

 

[코드]

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

    for i in range(1, len(land)):
        for j in range(4):
            if j == 0:
                dp[i][j] = land[i][j] + max(dp[i - 1][1], dp[i - 1][2], dp[i - 1][3])
            elif j == 1:
                dp[i][j] = land[i][j] + max(dp[i - 1][0], dp[i - 1][2], dp[i - 1][3])
            elif j == 2:
                dp[i][j] = land[i][j] + max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][3])
            else:
                dp[i][j] = land[i][j] + max(dp[i- 1][0], dp[i - 1][1], dp[i - 1][2])
    return max(dp[len(land) - 1][0], dp[len(land) - 1][1], dp[len(land) - 1][2], dp[len(land) - 1][3])