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

프로그래머스 땅따먹기

문제풀이

우선 그리디한 방법으로는 모든 경우를 포함하지 못하기 때문에 답을 찾을 수 없다. 그렇다면 완전탐색은 어떨까? O(4 * 3^N-1)이기 때문에 최악의 경우인 N = 100000일 때 시간초과가 예상된다. 그렇다면 이 문제는 어떻게 풀까?

각 행의 열 마다 최대 합을 갱신해 나가면 된다. 각 열의 최대 합은 이전 행에서 선택할 수 있는(같은 열은 선택할 수 없다.) 최대 값과 현재 열의 값을 더하면 된다. 결국 마지막 행에서 각 열을 선택했을 때 최댓값을 알 수 있게 된다. 또한 O(N)의 시간복잡도를 가지게 된다.

보통 이렇게 완전탐색이 힘든 경우에는 O(N)의 알고리즘을 먼저 생각해보면 되는 것 같다.

구현코드

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        
        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]));
        }
        
        for(int i = 0 ; i < 4 ; ++i){
            int value = land[land.length - 1][i];
            answer = value > answer ? value : answer;
        }
        
        return answer;
    }
}