[프로그래머스/Java] Lv.2 - 땅따먹기

프로그래머스 Lv.2 - 땅따먹기

요구사항

• N x 4 크기의 땅이 주어질 때 각 행에서 하나의 칸을 선택해 점수를 얻는 문제
• 같은 열을 연속으로 선택할 수 없다
• 선택한 칸들의 점수 합의 최댓값을 구하는 문제

접근 방식

DP(동적 프로그래밍) 로 풀었다.

점화식

dp[i][j] = max(dp[i-1][k]) + land[i][j]  (단, j != k)

→ 이전 행에서 같은 열이 아닌 것 중 최댓값 + 현재 칸의 값

핵심 아이디어

• dp[i][j]: i행 j열을 선택했을 때 누적 최댓값
• 이전 행(dp[i-1][k])에서 현재 열과 다른 열(j != k) 중 최댓값을 선택
• 마지막 행의 4개 값 중 최댓값이 정답

코드

import java.util.*;

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int row = land.length;
        int[][] dp = new int[row][4];

        for (int i = 0; i < 4; i++) {
            dp[0][i] = land[0][i];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    if (j == k) continue;
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][k] + land[i][j]);
                }
            }
        }

        for (int i = 0; i < 4; i++) {
            answer = Math.max(answer, dp[row-1][i]);
        }
        return answer;
    }
}

느낀점

• DP 문제는 점화식을 세우는 것 이 핵심이다.
• dp[i][j]에 누적 최댓값을 저장하는 방식으로 매 행마다 모든 경우를 다시 계산하지 않아도 된다.
• 열 제한 조건(j != k)을 3중 반복문으로 자연스럽게 처리할 수 있었다.
• DP를 코드로 구현하는 것보다 말로 설명하는 게 더 어렵다는 걸 느꼈다.
  점화식으로 정리해두는 습관을 기르자.