[프로그래머스] 땅따먹기 - Java(자바)

 

문제 이해

• 한 행씩 내려가면서 땅따먹는다. 점수 최대로 나오게 땅을 따먹어라
• 한 행씩 내려올 때 같은 열을 연속으로 밟을 수 없다.
• 예제에는 안나왔지만 같은 행에 같은 점수가 나올수 있고 그 점수가 최대값일수 있다고 생각해야한다.
• 한 행씩 내려오면서 연속된 열 제외 위 아래 열의 값을 더하여 dp[i][j] 에 나올 수 있는 max값을 배치한다.
• 마지막 행에 나오는 점수중 max값이 땅따먹기에서 나올 수 있는 최대의 점수이다.

import java.util.*;
class Solution {
    int solution(int[][] land) {
        int answer = 0;
        
        // 0행은 [0,0,0,0]
        int[][] dp = new int[land.length+1][4];
        
        for(int i = 1; i<land.length+1; 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], land[i-1][j] + dp[i-1][k]);
                    
                    answer = Math.max(dp[i][j], answer);
                }
            }
        }

        return answer;
    }
}