[프로그래머스] 땅따먹기 (JAVA/자바)

흶·2021년 9월 30일

알고리즘 프로그래머스

Algorithm

목록 보기

60/60

문제 링크

풀이

DP로 풀이하면 되는 문제이다.

가로의 길이가 4로 고정되어 있기 때문에 4가지의 case를 나누어서 dp 테이블을 채워주었다.

문제의 예제를 그림으로 표현하면 아래과 같다.

우선 첫번째 행은 원래 land 값으로 초기화 한다.
두번째 행부터 보는데, 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없다라는 규칙이 있기 때문에, 첫번째 그림처럼 같은 열을 제외한 다른 열의 값 중 가장 큰 값과 원래 값을 더해주면 된다! 이걸 모든 열에 대해 다 해주면 된다.
쭉쭉 내려가면 오른쪽과 같은 dp 테이블을 채울 수 있고, 마지막 행에서 가장 큰 값을 고르면 결과값을 구할 수 있다.

코드

class Solution {
    static int solution(int[][] land) {

        int n = land.length;

        int[][] dp = new int[n][4];
        for (int i = 0; i < 4; i++) {
            dp[0][i] = land[0][i];
        }

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][1], Math.max(dp[i - 1][2], dp[i - 1][3])) + land[i][0];
            dp[i][1] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][2], dp[i - 1][3])) + land[i][1];
            dp[i][2] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][3])) + land[i][2];
            dp[i][3] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][2])) + land[i][3];
        }

        int answer = Math.max(Math.max(dp[n-1][0], dp[n-1][1]), Math.max(dp[n-1][2], dp[n-1][3]));


        return answer;
    }
}