[lv2] 땅따먹기

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

 

dp로 현재 행렬을 밟았을 때 최대로 얻을 수 있는 값을 기록한다.

문제 조건에 따라, 이전 행에서 같은 열을 밟은 경우는 제외한다.

 

class Solution {
    int L;
    int[][] land, dp;

    void solve() {

        for(int i=1; i<L; i++) {
            for(int j=0; j<4; j++) {
                int max = 0;
                for(int k=0; k<4; k++) {
                    if(k!=j)
                        max = Math.max(max, dp[i-1][k]);
                    dp[i][j] = max + land[i][j];
                }
            }
        }
    }


    int solution(int[][] land) {
        int answer = 0;
        this.land = land;
        L = land.length;
        dp = new int[L][4];

        for(int i=0; i<4; i++)
            dp[0][i] = land[0][i];

        solve();

        for(int i=0; i<4; i++)
            answer = Math.max(answer, dp[L-1][i]);

        return answer;
    }
}