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

🔗 문제 링크

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

😮 문제 해결 방법

간단한 DP문제이다.

 

현재 스텝의 열에서 최대의 점수를 얻기 위해선 이전 스텝까지의 열 중에서 현재 내가 밟고 있지 않은 열의 최대 점수값을 더해준다.

만약 2번째 스텝의 1번째 열의 최대값을 구하고 싶다면, 1번째 스텝까지의 2,3,4열의 최대값에 현재 밟은 칸의 점수를 더해주면 최댓값이 된다.

 

이러한 방식을 통해 점화식을 세우면 dp[step][열] = arr[step][열] + max(dp[step-1][열에 해당하지 않는 열])이 된다.

dp[step-1][열에 해당하지 않는 열]의 경우 열이 4개가 있기 때문에 max안에 들어가는 dp의 개수는 3개이다.

 

마지막 칸까지 점수를 계산해주고 마지막 스텝에서의 최대값을 반환한다.

 

1. 1번째 스텝의 값으로 DP배열 초기화
2. 2번째 스텝부터 현재 스텝의 서있는 칸의 최대점수를 구한다.
   • 현재 스텝의 서있는 칸의 최대 점수 = 현재 스텝의 서있는 칸의 점수 + 이전 스텝까지의 서있는 칸을 제외한 최대점수
3. 마지막 단계까지 최대 점수를 구하고 그 중 최대 점수를 반환한다.

🚩 Java 코드

package com.second.algorithm.programmers;

public class Solution_12913_땅따먹기 {
    public static void main(String[] args) {
        int[][] land = {{1, 2, 3, 5}, {5, 6, 7, 8}, {4, 3, 2, 1}};

        int rst = solution(land);
        int rst2 = test(land);
        System.out.println(rst);
        System.out.println(rst2);
    }

    private static int test(int[][] land) {
        int[][] dp = new int[land.length][4];

        // dp 초기화
        System.arraycopy(land[0], 0, dp[0], 0, 4);

        recursive(1, dp, land);

        // 마지막 스텝에서의 최대값을 확인한다.
        int maxScore = 0;
        for (int score : dp[land.length - 1]) {
            maxScore = Math.max(maxScore, score);
        }

        return maxScore;
    }

    // 재귀
    private static void recursive(int step, int[][] dp, int[][] land) {
        if(step == land.length) return;

        dp[step][0] = land[step][0] + Math.max(dp[step - 1][1], Math.max(dp[step - 1][2], dp[step - 1][3]));
        dp[step][1] = land[step][1] + Math.max(dp[step - 1][2], Math.max(dp[step - 1][3], dp[step - 1][0]));
        dp[step][2] = land[step][2] + Math.max(dp[step - 1][3], Math.max(dp[step - 1][0], dp[step - 1][1]));
        dp[step][3] = land[step][3] + Math.max(dp[step - 1][0], Math.max(dp[step - 1][1], dp[step - 1][2]));

        recursive(step+1, dp, land);
    }

    private static int solution(int[][] land) {
        int[][] dp = new int[land.length][4];

        // dp 초기화
        System.arraycopy(land[0], 0, dp[0], 0, 4);

        // 현재 라인의 최대값은 (자신이 밟은 라인 + 자신이 밟은 라인을 제외한 이전의 스텝의 최대값)
        for (int step = 1; step < land.length; step++) {
            dp[step][0] = land[step][0] + Math.max(dp[step - 1][1], Math.max(dp[step - 1][2], dp[step - 1][3]));
            dp[step][1] = land[step][1] + Math.max(dp[step - 1][2], Math.max(dp[step - 1][3], dp[step - 1][0]));
            dp[step][2] = land[step][2] + Math.max(dp[step - 1][3], Math.max(dp[step - 1][0], dp[step - 1][1]));
            dp[step][3] = land[step][3] + Math.max(dp[step - 1][0], Math.max(dp[step - 1][1], dp[step - 1][2]));
        }

        // 마지막 스텝에서의 최대값을 확인한다.
        int maxScore = 0;
        for (int score : dp[land.length - 1]) {
            maxScore = Math.max(maxScore, score);
        }

        return maxScore;
    }
}