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

문제

아래로 내려가면서 점수를 가장 많이 얻을 수 있는 경우를 찾는 것이다. 하지만 같은 열을 반복해서 밟을 수는 없다.

 

---

풀이방법

풀이 시간 : 30분

풀이 방법 : DP

 

맨 처음에는 0번째 행에서 제일 큰값을 찾아서 아래에서 같은 열이 아닌것 중 가장 큰걸 찾으면 되는 줄 알았다.

근데 생각해보니 0번째 행에서 선택되는 값에 따라 달라진다는걸 알 수 있었다.

 

예를 들어,

1	2	9	10
8	7	9	11
5	4	8	8
2	3	4	4

 

라는 그래프가 있을때 내가 맨처음에 생각했던 방식은 위와 같다고 생각했는데,

 

1	2	9	10
8	7	9	11
5	4	8	8
2	3	4	4

위와같은 방식의 점수합이 더 크다는걸 알 수 있었다.

그래서 DP를 생각했고, 그냥 1번째 행부터 현재 0,1,2,3열에서 바로 윗 행의 가장 큰값을 더해오면 된다.

 

1행 0열에서 자신과 열이같은 바로 윗 점수를 제외하고 나머지 3개 중 최댓값을 더한다.

1행 1열도 동일하게 구한다.

이런식으로 구해나아가면 최종적으로 마지막에 최댓값을 구할 수 있다. 

---

코드

import java.util.*;
import java.io.*;

class Solution {
    int solution(int[][] land) {
        int size = land.length;
        
        for(int i = 1; i < size; 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]));
        }
        
        int max = Math.max(land[size-1][0], Math.max(land[size-1][1], Math.max(land[size-1][2], land[size-1][3])));
        
        return max;
    }
}