[프로그래머스/JAVA 자바] 땅따먹기

 

프로그래머스

문제풀이

i번째 행에서 특정 열이 선택되었을때 i-1 번째 행에서 i에서 선택한 열을 제외한 나머지 행의 값들 중 최대값을 구해서 더한다. (DP 의 메모이제이션(Memoization) 방법 )

 

land[ ][ ]	0	1	2	3
0	6	7	1	2
1	2	3	10	8
2	1	3	9	4
3	7	11	4	9

 

 

land[ ][ ]	0	1	2	3
0	6	7	1	2
1	9	9	17	15
2	1	3	9	4
3	7	11	4	9

 

land[ ][ ]	0	1	2	3
0	6	7	1	2
1	9	9	17	15
2	18	20	24	21
3	7	11	4	9

 

land[ ][ ]	0	1	2	3
0	6	7	1	2
1	9	9	17	15
2	18	20	24	21
3	31	35	25	33

 

구현코드

class Solution {
    int solution(int[][] land) {
        int answer = -1;

        for(int i=1;i<land.length;i++){
            land[i][0]+=Math.max(land[i-1][1],Math.max(land[i-1][2],land[i-1][3]));
            land[i][1]+=Math.max(land[i-1][0],Math.max(land[i-1][2],land[i-1][3]));
            land[i][2]+=Math.max(land[i-1][0],Math.max(land[i-1][1],land[i-1][3]));
            land[i][3]+=Math.max(land[i-1][0],Math.max(land[i-1][1],land[i-1][2]));
        }

        answer = Math.max(
                Math.max(land[land.length - 1][0], land[land.length - 1][1]),
                Math.max(land[land.length - 1][2], land[land.length - 1][3])
        );

        return answer;
    }
}