[백준] 17953. 디저트 - Java

🖇️ 문제 링크

17953번: 디저트

창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 '차라리 케이크를 먹는게 나았지 않았을까' 하는 식이다. 이럴 때 케이크를 다시 먹으면 좋겠지만, 창호는 건강을 위해 디저트는 하루에 한 가지만 먹기로 정해 놓았다. 어느 날 창호는 이런 '만족감'에 패턴이 있는 것을 알아냈다.

https://www.acmicpc.net/problem/17953

 

---

💡 문제 분석

💡

dp(day, prev) = 전날에 prev번째 디저트를 먹었을 때, day일 이후 얻을 수 있는 만족도

전 날에 먹은 디저트가 무엇인가에 따라 다음날 만족도가 바뀌기 때문에, 전날 먹은 디저트를 함께 메모이제이션합니다.

각 날마다 어떤 디저트를 먹어야 최대의 만족도를 얻을 수 있는지 비교 후 결정합니다.

 

 

---

⌨️ 코드

import java.io.*;
import java.util.*;

public class Q17953 {
    static int N, M;
    static int[][] dessert, cache;

    static int stoi(String s) { return Integer.parseInt(s); }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = stoi(st.nextToken());
        M = stoi(st.nextToken());
        dessert = new int[M][N];
        cache = new int[M][N];

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            Arrays.fill(cache[i], -1);
            for (int j = 0; j < N; j++)
                dessert[i][j] = stoi(st.nextToken());
        }

        System.out.println(dp(0, 0));
    }

    static int dp(int day, int prev) {
        if(day == N) return 0;

        int ret = cache[prev][day];
        if(ret != -1) return ret;

        ret = 0;
        for(int i = 0; i < M; i++) {
            if(day != 0 && i == prev)
                ret = Math.max(ret ,dp(day + 1, i) + dessert[i][day] / 2);
            else
                ret = Math.max(ret ,dp(day + 1, i) + dessert[i][day]);
        }
        return cache[prev][day] = ret;
    }
}

 

---

⏱️ 결과