[프로그래머스] 땅따먹기 - 자바(Java), DP(Dynamic Programming)

문제

https://programmers.co.kr/learn/courses/30/lessons/12913

풀이

DFS를 사용해 완전 탐색으로 풀이하면 시간 초과로 실패하기 때문에, DP(Dynamic Programming)를 사용하여 풀이해야 한다.

import java.util.*;

class Solution {
    int solution(int[][] land) {
        int n = land.length;

        for(int i = 1; i < n; i++) {
            //land[i][j] : i행 j열로 내려왔을 때의 최대 값
            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]));
        }

        return Arrays.stream(land[n-1]).max().getAsInt();
    }
}