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

문제

문제 해결

• 다이나믹 프로그래밍 활용

1. 한 행씩 땅을 밟아 얻는 점수를 저장할 배열을 생성한다.

2. 가장 아래 행부터 점수를 더해 갈 것이기 때문에 마지막 행의 값들을 dp배열의 마지막 행에 저장해준다. (처음으로 밟기 때문에 점수의 합은 원래 점수와 같음)

3. 가장 마지막 행의 바로 전 행부터 for문을 돌린다.

4. dp[i][0~3](현재행까지의 점수 합) = land[i][0~3](현재 행의 밟을 점수) + 현재 행 전까지의 점수 합들 중 가장 큰 점수 (단, 현재 열과 같은 열의 점수는 제외)

5. 모든 점수가 계산된 dp의 0번째 행중 가장 큰 점수를 구한다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] land) {
        final int COLS = 4;
        int rows = land.length;
        
        // dp 배열 생성
        int[][] dp = new int[rows][COLS];
        
        // 마지막 행의 값을 dp 배열에 복사
        for (int i = 0; i < COLS; i++) {
            dp[rows - 1][i] = land[rows - 1][i];
        }
        
        // 마지막 행의 바로 전 행부터 시작하여 dp 배열 채우기
        for (int i = rows - 2; i >= 0; i--) {
            dp[i][0] = land[i][0] + Math.max(Math.max(dp[i + 1][1], dp[i + 1][2]), dp[i + 1][3]);
            dp[i][1] = land[i][1] + Math.max(Math.max(dp[i + 1][0], dp[i + 1][2]), dp[i + 1][3]);
            dp[i][2] = land[i][2] + Math.max(Math.max(dp[i + 1][0], dp[i + 1][1]), dp[i + 1][3]);
            dp[i][3] = land[i][3] + Math.max(Math.max(dp[i + 1][0], dp[i + 1][1]), dp[i + 1][2]);
        }
        
        // dp의 첫 행에서 가장 큰 값 찾기
        int answer = 0;
        for (int i = 0; i < COLS; i++) {
            answer = Math.max(answer, dp[0][i]);
        }

        return answer;
    }
}