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

Link | 12913번 문제 : 땅따먹기

📌 Analyze

Row를 차례대로 탐색하면서 DP로 해결하면 된다.

R 번째 row에서는 R - 1의 row 값을 참고하여 계산한다.

이때 (R, C) += R - 1 row의 최댓값을 하면 된다.

주의할 점은 같은 열이 연속으로 더해질 수 없다는 것이다.

(R, C)의 값을 구할 때 (R - 1, C) 값을 제외하고 최댓값을 찾는다.

📌 Code

GitHub Repository

Solution

class Solution {
    public int solution(int[][] land) {
        int R = land.length;
        for (int r = 1; r < R; r++) {
            land[r][0] += Math.max(land[r - 1][1], Math.max(land[r - 1][2], land[r - 1][3]));
            land[r][1] += Math.max(land[r - 1][0], Math.max(land[r - 1][2], land[r - 1][3]));
            land[r][2] += Math.max(land[r - 1][0], Math.max(land[r - 1][1], land[r - 1][3]));
            land[r][3] += Math.max(land[r - 1][0], Math.max(land[r - 1][1], land[r - 1][2]));
        }
        return Arrays.stream(land[R - 1]).max().orElseThrow();
    }
}