땅따먹기

문제

풀이

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

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

문제가 애초에 테스트케이스를 제한적으로 줘서 잘 보고 이해해야함. 문제에서 요구하는 것은 결국 마지막에 가장 큰 값을 출력해야 한다는 것이다.

행의 개수가 10만까지라서 DFS로 양방향밑으로 가면서 모든 경우를 탐색해서 최댓값을 찾는 방식은 매우 비효율적이다. DFS가 비효율 적이라면 무조건 DP
최대값을 챙기면서, 결국에 마지막에는 가장 큰 값을 가져야함 -> DP

그렇기 때문에 4x4의 land가 있다고 치면, 2행에는 이전 행(1행)에서부터의 현재 열의 위치를 제외한 나머지 열중에서 최대값을 구해서 현재의 2행부터 4행까지 가주면 된다.