땅따먹기

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

 

프로그래머스

 

 

처음엔 문제를 너무 대충 봐서.. 한 라인에서 최대값을 찾고, 그 다음 라인에선 윗 라인의 열을 제외한 최대값을 찾고.. 

주어진 테스트 케이스는 통과했는데, 제출했더니 0점이더라. ...

 

dp를 이용해 다시 풀었다.

 

 

class Solution {
    int solution(int[][] land) {
        
        int[][] sum = new int[land.length][land[0].length];
        for (int i = 0; i < 4; i++) {
            sum[0][i] = land[0][i];
        }
        
        for (int i = 0; i < land.length - 1; i++) {
            
            for (int j = 0; j < land[i].length; j++) {
                
                for (int k = 0; k < land[i + 1].length; k++) {
                    
                    if (j == k) continue;
                    
                    sum[i + 1][k] = Math.max(sum[i + 1][k], (sum[i][j] + land[i + 1][k]));
                    
                }
                
            }
            
        }
        
        int max = 0;
        for (int i = 0; i < 4; i++) {
            max = Math.max(sum[sum.length - 1][i], max);
        }
        
        return max;
    }
}