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

문제

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

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

풀이

2차원 DP로 문제를 해결할 수 있었다.

DP[i][j]를 좌표 (i, j)까지 도달하여 얻을 수 있는 가장 큰 점수라고 가정했을 때 이전 행에서와 같은 열을 지나오지 못하므로 j의 값에 따른 4개의 분기를 처리해주었다.

일단 DP 테이블을 채우기위해서 0번째 행의 초기값을 세팅해주었고 1행부터는 이전 행에서 현재의 j 값과 다른 모든 값을 비교하여 최댓값을 구해주면 그게 곧 좌표 (i, j)까지 도달하여 얻을 수 있는 가장 큰 점수가 된다.

그렇게 모든 좌표에 대해 DP 테이블에 값을 채워주고 마지막행의 점수들이 가장 큰 것이 확실하니까(모든 땅의 점수가 양수) 마지막행 4개의 열에 대해서 최댓값을 구해주면 정답을 구할 수 있다.

코드

class Solution {

    int dp[][] = new int[100001][4];

    int solution(int[][] land) {

        int answer = 0;

        // Initial Setting
        for(int i = 0; i < 4; i++) {
            dp[0][i] = land[0][i];
        }

        // DP
        for(int i = 1; i < land.length; i++) {
            for(int j = 0; j < 4; j++) {
                if(j == 0) {
                    dp[i][0] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][3]) + land[i][j];
                } else if(j == 1) {
                    dp[i][1] = Math.max(Math.max(dp[i - 1][0], dp[i - 1][2]), dp[i - 1][3]) + land[i][j];
                } else if(j == 2) {
                    dp[i][2] = Math.max(Math.max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][3]) + land[i][j];
                } else if(j == 3) {
                    dp[i][3] = Math.max(Math.max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]) + land[i][j];
                }
            }
        }

        // Get Max Value
        for(int i = 0; i < 4; i++) {
            answer = Math.max(dp[land.length - 1][i], answer);
        }

        return answer;
    }
}