[프로그래머스,Level 2] 땅따먹기 (JAVA 구현)

- 첫 풀이 및 정답풀이

  이 문제는 처음 읽자마자 dp를 활용해야 하는 문제인 것을 알 수 있었다. 한 줄의 선택 횟수는 1번이고, 다음 줄에선 이전 줄에서 선택한 열의 숫자는 선택하지 못한다는 제약사항이 존재한다. 

 

  이러한 규칙 속에서 dp를 위한 점화식을 세워보면, x번째 행에서 0번째 열은 이전 행의 값들 중 가장 큰 값을 선택하고 와야 한다. 그렇기에 dp [x][0] = max(dp [i-1][1], dp [i-1][2], dp [i-1][3]) + land [x][0]와 같은 식이다. 이 과정을 n번째 행까지 수행하면, 각각의 경우의 수들 중 최댓값들이 저장되어 있으며 그 중에서도 가장 큰 값이 문제가 원하는 답이다.

 

class Solution {
    int solution(int[][] land) {
        
        int answer = Integer.MIN_VALUE;
        // 1. n개의 행 존재.
        int n = land.length;
        // 2. dp배열 선언.
        int[][] dp = new int[n][land[0].length];        
        // 3. land의 0번째 행은 그대로 dp의 0번째 행에 저장.
        for(int i = 0 ; i < land[0].length;i++)
            dp[0][i] = land[0][i];        
        // 4. 1번째 행부터 반복.
        for(int i = 1;i<n;i++){
            for(int j =0;j<land[i].length;j++){
                int max = Integer.MIN_VALUE;
                // 5. i의 이전 행을 탐색.
                for(int k=0;k<4;k++){
                    // 6. 현재 열(j)과 이전 열(k)이 같다면 고려하지 않는다.
                    if(j == k) continue;
                    // 7. 하나의 열을 제외한 나머지 열에서 최댓값을 찾아 저장.
                    max = Math.max(max,dp[i-1][k]);
                }
                // 8. 해당 최댓값과 현재 땅의 값을 더해 dp에 저장.
                dp[i][j] = land[i][j] + max;
            }
        }
        
        // 9. n-1번째 행에 저장된 최댓값들 중 가장 큰 값을 answer에 저장.
        for(int i=0;i<4;i++)
            answer = Math.max(answer,dp[n-1][i]);
        
        
        return answer;
    }
}