회전초밥(SUSHI) 정답 코드

난이도 ★★★★★

문제를 보시려면 여기를 클릭

힌트

동적계획법으로 완전탐색만 하면 답은 나오지만, 입력이 클 때 Recursive call이 너무 많아져서 메모리가 나가버린다.  → 가능할 때까지 탐욕(Greedy), 불가능할 때부터는 동적계획법(Dynamic Programming)으로 완전 탐색

이하는 코드입니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
typedef struct {
    int price;
    int pref;
} Sushi;
 
int n;
Sushi sushi[20];
int* cache;
 
int getMaxPref(int budget) {
    int& ret = cache[budget];
    if (ret != -1) {
        return ret;
    }
 
    int maxPref = 0;
    for (int i = 0; i < n; i++) {
        if (sushi[i].price <= budget) {
            int partialMaxPref = sushi[i].pref + getMaxPref(budget - sushi[i].price);
            maxPref = MAX(maxPref, partialMaxPref);
        }
    }
 
    return ret = maxPref;
}
 
int getGcd(int a, int b) {
    if (b == 0) {
        return a;
    }
 
    getGcd(b, a % b);
}
 
int getLcm(int a, int b) {
    return (a * b) / getGcd(a, b);
}
 
int main() {
    int c;
    scanf("%d\n", &c);
 
    while (c-- > 0) {
        int m;
        scanf("%d %d", &n, &m);
        m /= 100;
 
        // get input and get best sushi
        int bestSushiIndex = -1;
        float bestSushiRate = 0.0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &sushi[i].price, &sushi[i].pref);
            sushi[i].price /= 100;
            
            float rate = (float)sushi[i].pref / sushi[i].price;
            if (rate > bestSushiRate) {
                bestSushiIndex = i;
                bestSushiRate = rate;
            }
        }
 
        // get lcm
        int lcm = sushi[0].price;
        for (int i = 1; i < n; i++) {
            lcm = getLcm(lcm, sushi[i].price);
        }
 
        // if m is enough to be divided lcm, do greedy
        int maxPref = 0;
        if (lcm < m) {
            int amount = m / lcm;
            amount *= (lcm / sushi[bestSushiIndex].price);
 
            maxPref = sushi[bestSushiIndex].pref * amount;
            m = m - sushi[bestSushiIndex].price * amount;
        }
 
        // do dynamic programming
        cache = (int*)malloc(sizeof(int) * (m + 1));
        for (int i = 0; i <= m; i++) {
            cache[i] = -1;
        }
        cache[0] = 0;
 
        maxPref += getMaxPref(m);
        free(cache);
 
        printf("%d\n", maxPref);
    }
    
    return 0;
}