[연습문제 / 프로그래머스] 12913번 : 땅따먹기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12913

 

Lv2 문제이고, 스스로 푼 문제다!

이전에 다이나믹 프로그래밍 풀 때 접했던 문제랑 비슷했다. 그동안의 최댓값을 dp의 각 위치에 누적한 다음 마지막 행에서 최댓값을 구하면 된다 

 

문제 이해 

dp의 (i, j) 위치에는 0부터 i -1행의 수 중 j열이 아닌 값 중에서 제일 큰 값을 누적한 값이 저장되어 있다 

1. 초기화로 0행에 있는 수들을 dp 행렬의 0행에 저장한다

2-1. 1행부터 시작해 land의 (i,j)의 값은 미리 dp[i][j]에 넣어준다 

2-2. i -1 행의 j열을 뺀 나머지 열 중에서 최댓값을 max_num에 누적한다

3. 전 행에서의 j열을 제외한 최댓값을 dp[i][j]에 누적한다 

4. dp의 마지막 행에서 최댓값을 출력해준다 

 

- 정답 풀이 : 

def solution(land):
    n = len(land)
    
    dp = [[0] * 4 for _ in range(n)]
    for i in range(4):
        dp[0][i] = land[0][i]
        
    for i in range(1, n):
        for j in range(4):
            max_num = 0
            dp[i][j] += land[i][j]
            for k in range(4):
                if k != j:
                    max_num = max(dp[i - 1][k], max_num)
                    
            dp[i][j] += max_num
            
    return max(dp[-1])