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

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

코딩테스트 연습 - 땅따먹기

 

풀이

 

이 문제는 전형적인 DP문제입니다.

저는 2차원 배열을 이용해서 문제를 해결했습니다!

같은 열을 바로 밟을 수 없기 때문에 저는 매 행마다 4개의 열 각각에 대해서 최대값을 따로 저장하면서 아래로 내려오는 방식으로 코드를 짰습니다.

 

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int len = land.length;
        int[][] dp = new int [len][4];
        
        //dp[0][] 초기화
        for(int i=0; i<4; i++){
            dp[0][i] = land[0][i];
        }
        //dp[1~len-1][]
        for(int i=1; i<len; i++){
            dp[i][0] = Math.max(Math.max(dp[i-1][1], dp[i-1][2]), dp[i-1][3]) + land[i][0];
            dp[i][1] = Math.max(Math.max(dp[i-1][0], dp[i-1][2]), dp[i-1][3]) + land[i][1];
            dp[i][2] = Math.max(Math.max(dp[i-1][0], dp[i-1][1]), dp[i-1][3]) + land[i][2];
            dp[i][3] = Math.max(Math.max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]) + land[i][3];
        }

        //맨 아래줄의 4개의 열중에 최댓값 찾기
        answer = Math.max(Math.max(dp[len-1][0], dp[len-1][1]), Math.max(dp[len-1][2], dp[len-1][3]));

        return answer;
    }
}