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

처음 문제를 봤을 때 DFS로 구현해야겠다는 생각을 했다.

아직 DFS에 적응이 된 게 아니어서 더듬더듬 구현했는데 시간 초과 판정을 받았다...

아마 n이 100,000 정도로 커지면서 시간 초과가 난것으로 생각된다..

풀이 방법이 떠오르지 않아서 결국 검색을 통해 힌트를 얻었다.

 

DP를 이용하여 간단히 풀었다...

코드를 이해하는데는 오래 걸리지 않았지만 익숙하지 않기도 하고.. 비슷한 문제를 만났을 때 DP로 해결할 수 있을까...

따로 정리가 필요하다고 느꼈다.

---

최종 코드

import java.util.Arrays;
class Solution {
    int solution(int[][] land) {
        int answer = 16;
        
        // DP를 이용하여 최댓값 구하기
        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][1], Math.max(land[i-1][0], land[i-1][3]));
            land[i][3] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][2]));
        }

        int[] temp = land[land.length-1];
        Arrays.sort(temp);
        answer = temp[3];

        return answer;
    }
}