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

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/12913?language=java

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네 번째 칸 (5)를 밟았으면, 2행의 네 번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return 하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네 번째 칸 (5), 2행의 세 번째 칸 (7), 3행의 첫 번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한 사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land	answer
[[1, 2, 3, 5], [5, 6, 7, 8], [4, 3, 2, 1]]	16

입출력 예 설명

입출력 예 #1

• 문제의 예시와 같습니다.

 

내가 작성한 코드

class Solution {
    int solution(int[][] land) {
        // 최종 점수를 저장한 변수 생성
        int answer = 0;
        // 배열의 길이 저장
        int len = land.length;
        
        // 반복문 진행하면서 최대값 구하기, 누적 최댓값 구하기
        for (int i = 1; i < len; i++) {
            land[i][0] += Math.max(Math.max(land[i-1][1], land[i-1][2]), land[i-1][3]);
            land[i][1] += Math.max(Math.max(land[i-1][0], land[i-1][2]), land[i-1][3]);
            land[i][2] += Math.max(Math.max(land[i-1][0], land[i-1][1]), land[i-1][3]);
            land[i][3] += Math.max(Math.max(land[i-1][0], land[i-1][1]), land[i-1][2]);
        }
        
        // 마지막 행 변수
        int lastRow = len -1;
        // 마지막 행에서 가장 큰 값이 정답
        for (int j = 0; j < 4; j++) {
            answer = Math.max(answer, land[lastRow][j]);
        }
        
        // 정답 반환
        return answer;
    }
}

문제를 풀기 위해 생각한 방향

처음 문제를 봤을 때는 각 행에서 이전 열만 밟지 않으면 되니까, 단순히 매 행마다 가장 큰 값을 고르면 된다고 생각했다. 그래서 이전에 선택한 열을 oldColumn 변수로 저장해두고, 현재 행에서 그 열을 제외한 값들 중 가장 큰 수를 더해 나가는 방식으로 구현했다. 즉, 매 순간의 최댓값을 선택하는 그리디(탐욕적) 접근이었다.

하지만 코드를 작성하고 곰곰이 생각해보니, “이 방식이 항상 최선일까?” 하는 의문이 들었다. 만약 한 행에서 큰 값을 선택한 탓에, 다음 행에서 훨씬 더 큰 값을 놓치는 상황이 발생한다면 전체 합은 최댓값이 아닐 수도 있다는 점을 깨달았다. 실제로 반례를 만들어보니, 첫 번째 행에서 가장 큰 값을 고르는 것이 오히려 다음 행의 선택 폭을 줄여 전체 합이 작아지는 경우가 있었다. 이 지점에서 그리디 방식은 국소 최적해(local optimum)에 머물 뿐, 전역 최적해(global optimum)를 보장하지 못한다는 사실을 확인했다.

이 문제는 결국 “현재의 선택이 다음 선택에 영향을 준다”는 구조를 가지고 있었다. 그렇다면 단순히 한 행만 보는 것이 아니라, 이전 행에서의 결과를 누적해서 고려해야 했다. 여기서 바로 동적 계획법(DP, Dynamic Programming) 이 필요하다는 결론에 도달했다.

DP로 접근하기 위해 먼저 상태를 정의했다. dp[i][j]를 “i번째 행의 j열을 밟았을 때 얻을 수 있는 최대 점수”로 두었다. 그리고 현재 위치까지 올 수 있는 모든 경로 중, 바로 윗행에서 같은 열을 제외한 곳 중 최댓값을 더해주는 점화식을 세웠다.

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

이 식을 기반으로 2행부터 마지막 행까지 차례로 누적 계산을 진행하면, 마지막 행에는 각 경로별로 가능한 최댓값이 저장된다. 따라서 마지막 행에서 가장 큰 값을 찾으면 그것이 곧 정답이 된다.

이 방식은 그리디 접근의 한계를 보완하며, 매 행의 가능한 선택을 모두 고려해 최적해를 찾을 수 있다. 문제를 해결하면서 “항상 가장 커 보이는 값을 고른다고 해서 최적의 결과가 되지는 않는다”는 점을 배웠고, 현재 선택이 미래의 가능성에 어떤 제약을 주는지를 고려해야 한다는 걸 다시 한번 느꼈다.
앞으로 비슷한 유형의 문제를 만나면, 단순한 최댓값 선택보다 이전 상태를 기반으로 한 누적 최적화(DP 사고) 를 먼저 떠올릴 수 있도록 하는 것이 이번 학습의 핵심이었다.