[백준] 17953. 디저트

문제 링크

[백준] 17953. 디저트

풀이 과정

다이나믹 프로그래밍 문제입니다. 전날 먹은 디저트를 오늘 또 먹게되면 만족감이 반으로 감소되므로, 오늘 어떤 디저트를 먹는다고 하면, 전날 해당 디저트를 먹었을 때의 먹지 않았을 때를 구분지어야 했습니다.

for (int i = 0; i < dessert.length; i++) {
    dp[i][0] = dessert[i][0];
}

0번째 날은 전날의 영향을 받지 않으므로, 각 디저트의 만족감이 곧 최대 만족도가 됩니다. 여기서 dp[i][j] 는 j 날 i 디저트를 먹었을 때의 최대 만족감을 의미합니다.

for (int day = 1; day < N; day++) {
    for (int type = 0; type < M; type++) {
        for (int eachType = 0; eachType < M; eachType++) {
            if (eachType == type)
                dp[type][day] = Math.max(dp[type][day], dp[eachType][day - 1] + dessert[type][day] / 2);
            else
                dp[type][day] = Math.max(dp[type][day], dp[eachType][day - 1] + dessert[type][day]);
        }
    }
}

이제 1번째 날부터 N - 1 번째 날까지 Bottom-up 방식으로 dp 배열을 채워갈 겁니다. 각 day 날에 먹는 type 이라는 디저트에 대해 dp[type][day] 를 다음과 같은 방법으로 구해 최대값을 갱신시켜 줍니다.

• 전날 먹은 각각의 디저트 eachType 에 대해 오늘 먹을 type 과 같다면 반감된 만족도를 적용해 최대 만족도를 구하고,
• 오늘 먹을 type 과 다르다면 온전한 만족도를 더해 최대 만족도를 구합니다.

코드

import java.util.Scanner;

public class Main {
    static int N, M;
    static int[][] dessert;
    static int[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        dessert = new int[M][N];
        dp = new int[M][N];

        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++)
                dessert[i][j] = sc.nextInt();

        for (int i = 0; i < dessert.length; i++) {
            dp[i][0] = dessert[i][0];
        }

        for (int day = 1; day < N; day++) {
            for (int type = 0; type < M; type++) {
                for (int eachType = 0; eachType < M; eachType++) {
                    if (eachType == type)
                        dp[type][day] = Math.max(dp[type][day], dp[eachType][day - 1] + dessert[type][day] / 2);
                    else
                        dp[type][day] = Math.max(dp[type][day], dp[eachType][day - 1] + dessert[type][day]);
                }
            }
        }

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

        System.out.println(answer);
    }
}