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

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

프로그래머스

 

---

 

문제 개요

'땅따먹기' 게임은 N행 4열로 이루어진 땅(land)에서 진행됩니다. 각 칸에는 점수가 적혀 있고, 1행부터 N행까지 내려가면서 한 번에 하나의 칸을 밟아 내려가야 합니다. 단, 같은 열을 연속해서 밟을 수 없는 규칙이 있습니다. 우리가 해야 할 일은, 주어진 땅에서 점수를 최대화할 수 있도록 게임을 진행하며, 마지막 행에 도달할 때 얻을 수 있는 최대 점수를 구하는 것입니다.

 

 

접근 방법

이 문제는 **동적 계획법(DP)**을 활용하여 해결할 수 있습니다. 각 행에서 선택할 수 있는 칸의 점수는 이전 행에서 선택한 열을 제외한 나머지 열에서 가장 큰 값을 더하는 방식으로 점수를 갱신할 수 있습니다.

1. DP 배열 사용

먼저, land[i][j]에 저장된 점수에 대해서, land[i][j]를 선택했을 때의 최대 점수를 계산해야 합니다. 이를 위해, 각 행에서 어떤 열을 선택할 때 얻을 수 있는 최대 점수를 저장하는 배열을 사용합니다.

• dp[i][j]는 i행에서 j열을 선택했을 때의 최대 점수입니다.
• 각 행의 칸을 선택할 때, 이전 행에서 같은 열을 제외한 나머지 열에서 얻을 수 있는 최대 점수를 더해주면 됩니다.

2. 이전 행의 최댓값 계산

각 행에서 j열을 선택할 때, i-1행에서 j열을 제외한 열들 중에서 가장 큰 값을 선택하여 더해주어야 합니다. 이를 통해 점수를 갱신해나갑니다.

 

class Solution {
    int solution(int[][] land) {
        int n = land.length;
        
        // 첫 번째 행부터 시작하여 점수를 갱신해 나갑니다.
        for (int i = 1; i < n; i++) {
            // 이전 행의 각 열을 기준으로, 같은 열을 제외한 최대값을 더해줍니다.
            for (int j = 0; j < 4; j++) {
                int maxPrev = 0;
                for (int k = 0; k < 4; k++) {
                    if (j != k) {
                        maxPrev = Math.max(maxPrev, land[i - 1][k]);
                    }
                }
                land[i][j] += maxPrev;
            }
        }
        
        // 마지막 행에서의 최대값을 구합니다.
        int answer = 0;
        for (int j = 0; j < 4; j++) {
            answer = Math.max(answer, land[n - 1][j]);
        }
        
        return answer;
    }
}