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

프로그래머스

동적 계획법(Dynamic Programming, DP) 문제이다. 처음에 DFS로 테스트 케이스를 풀어내긴 했는데 인풋 최대값이 100,000이다보니 실제 채점에서는 전부 통과되지 않아 DP로 바꾸어 풀게되었다. DP는 '기억하며 풀기'로 보통 바꾸어 말하는데 반복되는 문제에 대한 최적의 결과를 단계별로 메모리에 저장하고 이를 활용하여 다음 단계의 결과를 구하는 방식으로 사용한다. 여기서는 땅따먹기의 각 단계별로 직전단계까지의 최대값을 저장(또는 land에 바로 더해주기)하는 방식으로 DP를 구현했다.

 

- 1번 행부터 마지막 행까지 탐색하며:

1) 직전 단계에서 같은 열을 제외한 모든 숫자들의 최대값을 구함

2) 현 단계의 각 열에 직전 단계의 최대값을 더함

- 마지막 행을 돌며 최대값을 구하여 반환 

 

Note

- 인풋의 복잡도를 고려하여 시간초과 나올 것 같으면 빨리 다른 방법을 찾자

- DP에 대해 자세하게 정리해봐야겠다.

class Solution {
    int solution(int[][] land) {

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