땅따먹기

문제

N행 4열로 이루어진 땅이 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 가지 규칙이 있습니다. 연속해서 같은 열을 밟을 수 없습니다. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하는 문제입니다.

• 입력: N행 4열로 이루어진 2차원 정수 배열 land (N은 100,000 이하의 자연수)
• 출력: 마지막 행까지 내려왔을 때 얻을 수 있는 최대 점수를 반환합니다.

링크: https://school.programmers.co.kr/learn/courses/30/lessons/12913

풀이: 2차원 배열을 활용한 다이나믹 프로그래밍 (DP)

이전 행에서 선택한 열에 따라 현재 행에서 선택할 수 있는 열이 제한되는 조건이 있으므로, 각 위치까지 도달했을 때의 최적해(최대 점수)를 누적해 나가는 DP 방식으로 해결합니다.

• 상태 정의: d[i][j]를 i번째 행에서 j번째 열을 밟았을 때 얻을 수 있는 최대 점수라고 정의합니다.
• 초기화: 0번째 행의 점수들은 이전 행의 제약이 없으므로, 주어진 land 배열의 첫 번째 행 값을 그대로 d[0]에 복사합니다.
• 점화식 도출: 1번째 행부터 N-1번째 행까지 순회합니다. 현재 i행 j열을 밟기 위해서는, 바로 위 행(i-1)에서 j열이 아닌 다른 열(k)을 밟았어야 합니다. 따라서 이전 행의 다른 세 열 중에서 가장 큰 값(max)을 찾고, 그 값에 현재 칸의 점수 land[i][j]를 더해 d[i][j]에 저장합니다.
• 최댓값 갱신: 배열의 마지막 행(i == land.length - 1)을 계산할 때, 나올 수 있는 각 열의 누적 점수 중 가장 큰 값을 ans에 갱신하여 최종 정답으로 도출합니다.

코드

class Solution {
    int solution(int[][] land) {
        int[][] d = new int[land.length][4];
        
        for (int i = 0; i < 4; i++) {
            d[0][i] = land[0][i];
        }
        
        int ans = 0;
        for (int i = 1; i < land.length; i++) {
            for (int j = 0; j < 4; j++) {
                int max = 0;
                // 이전 행(i-1)에서 같은 열(j)이 아닌 값 중 최댓값 탐색
                for (int k = 0; k < 4; k++) {
                    if (j == k) continue;
                    max = Math.max(max, d[i - 1][k]);
                }
                
                // 이전 행의 최댓값 + 현재 칸의 점수 누적
                d[i][j] = max + land[i][j];
                
                // 마지막 행인 경우 정답 갱신
                if (i == land.length - 1) {
                    ans = Math.max(ans, d[i][j]);
                }
            }
        }
        
        return ans;
    }
}

알고리즘 분류

다이나믹 프로그래밍 (Dynamic Programming)