[AlgoSpot][Python] 회전초밥

📒 문제 설명

🔖 https://www.algospot.com/judge/problem/read/SUSHI

📖 문제
문제 풀이 내기에서 모인 벌금이 많이 쌓여서 알고스팟 운영진들은 회식을 하러 회전초밥집에 갔습니다. 회전초밥집에 들어선 운영진들은 초밥은 먹지 않고 전략 회의를 시작했습니다. 회전초밥집에는 n종류의 메뉴가 있는데, 운영진들은 각 메뉴에 대해 선호도를 매겼습니다.

초밥	계란	연어	장어	대뱃살	스테이크	후라이드 치킨
선호도	7	9	10	12	20	1

운영진들은 주어진 예산 안에서 선호도의 합을 최대한으로 하도록 초밥을 먹고 싶습니다. 각 종류의 초밥은 무한정으로 공급된다고 가정합시다. 이 때 얻을 수 있는 최대한의 선호도는 얼마일까요?

✍ 입력
입력의 첫 줄에는 테스트 케이스의 수 c(1 <= c <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 초밥의 종류 n(1 <= n <= 20)과 운영진들의 예산 m (1 <= m <= 2,147,483,647)이 주어집니다. 그 후 n 줄에 각 초밥의 가격과 선호도가 순서대로 주어집니다. 가격은 20,000 이하의 자연수로, 항상 100 의 배수입니다. 선호도는 20 이하의 자연수입니다.

💻 출력
각 테스트 케이스별로 한 줄에 가능한 선호도의 최대 합을 출력합니다.

---

✏️ 풀이 과정

📝 1차 시도

• 처음에는 기본적인 Fractional Knapsack Problem으로 생각하고, 가격 대비 선호도가 가장 높은 초밥만 담는 방식의 그리디 알고리즘으로 접근하였다.

• 그리디 알고리즘으로만 풀이하면, 예산을 다 소비하지 못하는 경우가 발생한다. 주어진 테스트 케이스인 (2500, 7), (3000, 9), (4000, 10), (5000, 12), (10000, 20), (15000, 1)의 경우 3000원짜리 초밥의 가성비가 가장 좋은데, 3000원짜리 초밥만 세 접시를 담는 것보다, 3000원짜리 초밥 두 접시와 4000원짜리 초밥 한 접시를 담는 것이 선호도의 합이 더 크다.

• 우선 그리디 알고리즘으로 풀이하는 방법은 제쳐두고, 0/1 Knapsack Problem처럼 메모이제이션을 적용하여 아래 코드를 작성했다. 최대 입력이 매우 크기 때문에 아래 풀이는 적절하지 않을 것이고, 역시 시간 초과가 발생하였다.

✨ 소스 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

def solve(budget):
    ans = cache[budget]
    if ans != -1:
        return ans

    ans = 0
    for d in dishes:
        if budget < d[0]: continue
        ans = max(ans, solve(budget - d[0]) + d[1])

    cache[budget] = ans
    return ans

for _ in range(int(input())):
    N, M = map(int, input().split())
    dishes = []
    cache = [-1] * (M + 1)

    for _ in range(N):
        dishes_info = input().split()
        # dishes[i][0]: 가격, dishes[i][1]: 선호도
        dishes.append((int(dishes_info[0]), int(dishes_info[1])))

    print(solve(M))

---

📝 2차 시도

• 최대 입력이 너무 크기 때문에 메모리 공간을 어떤 방법으로든 줄일 필요가 있어보인다. 교재를 참고하여 반복적 동적 계획법을 사용하여 코드를 작성하였다.

• 초밥의 최대 가격은 20,000원을 넘지 않으므로, dp[budget] 이후를 구하는 과정에서 dp[budget - 20000] 이전의 원소는 필요하지 않다. 따라서 슬라이딩 윈도 기법을 적용하기 적절하다. budget을 증가시켜 감에 따라 dp[]의 마지막 2만 개 원소들만을 항상 저장하는 방식이다.

• 슬라이딩 윈도 기법을 구현하기 위해서 20,001 크기의 배열을 생성하고, 이 배열에 접근할 때 항상 인덱스의 20,001에 대한 나머지를 취했다.

• 모든 초밥의 가격이 100의 배수라는 조건이 있고, 그렇다면 예산의 100원 이하의 자투리도 필요하지 않으므로 모든 가격을 100으로 나누어도 무방하다. 따라서 배열의 크기도 201로 줄일 수 있다.

• 위와 같은 과정을 거쳐도 Python으로 작성한 코드로는 시간 초과가 발생하여, C++로 작성하여 제출했더니 정답으로 처리되었다.

✨ 소스 코드

import sys
input = sys.stdin.readline

def solve():
    ans = 0
    dp = [0] + [-1] * 200
    for budget in range(1, M + 1):
        cand = 0
        for d in dishes:
            if budget >= d[0]:
                cand = max(cand, dp[(budget - d[0]) % 201] + d[1])
        dp[budget % 201] = cand
        ans = max(ans, cand)
    return ans

for _ in range(int(input())):
    N, M = map(int, input().split())
    M //= 100
    dishes = []

    for _ in range(N):
        dishes_info = input().split()
        # dishes[i][0]: 가격, dishes[i][1]: 선호도
        dishes.append((int(dishes_info[0]) // 100, int(dishes_info[1])))

    print(solve())

✨ 소스 코드 (C++)

#include <iostream>

using namespace std;
int N, M;
int price[20], pref[20];
int dp[201];

int solve() {
    dp[0] = 0;
    for (int budget = 1; budget <= M; budget++) {
        int cand = 0;
        for (int dish = 0; dish < N; dish++)
            if (budget >= price[dish])
                cand = max(cand, dp[(budget - price[dish]) % 201] + pref[dish]);
        dp[budget % 201] = cand;
    }
    return dp[M % 201];
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> N >> M;
        M /= 100;
        for (int i = 0; i < N; i++) {
            cin >> price[i] >> pref[i];
            price[i] /= 100;
        }
        cout << solve() << endl;
    }
}

---

📝 3차 시도 (미해결)

• 그리디 알고리즘과 동적 계획법을 결합하여 사용하면 실행 시간을 획기적으로 줄일 수 있을 것으로 생각했다. 예산이 너무 큰 경우, 먼저 가성비가 좋은 초밥을 일정 수준까지 고르는 것은 논리적으로 어색함이 없다고 생각했기 때문이다.

• 그리디 알고리즘을 적용하기 위하여, 각 초밥의 가격을 선호도로 나누어 큰 순서대로 정렬한 sorted_dishes 배열을 사용하였다.

• 초밥의 가격은 20,000원을 넘을 수 없으므로, max_cost는 200으로 설정하였고, max_cost인 초밥을 몇 접시 살 수 있을만큼만 예산을 남겨두고, 가성비가 좋은 초밥만을 구매하도록 했다. 아래 코드에서는 하한을 열 접시로 설정했다.

• 남은 예산으로 살 수 있는 초밥들의 조합 중 최대 선호도를 만족하는 경우는 1차 시도에서 풀이한 동적 계획법을 적용하였고, 실제로 실행 시간이 크게 줄었다. 다만 동적 계획법을 적용하기 전, 예산을 얼마나 남겨두어야 하는지에 대한 기준이 애매모호하다.

• 따라서 이 문제를 그리디하게 해결할 수 있는 것은 맞는지, 사이트에 등록된 테이스 케이스에 대해서만 통과되는 것인지, 모든 경우에 대하여 만족하는 예산의 하한이 존재하는 지에 대한 검증이 필요하다.

✨ 소스 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

def greedy():
    global M, cache
    ans = 0
    max_cost = 200

    if M > max_cost * 10:
        num_dishes = (M - max_cost * 10) // sorted_dishes[0][0]
        ans += num_dishes * sorted_dishes[0][1]
        M -= num_dishes * sorted_dishes[0][0]

    cache = [-1] * (M + 1)
    return ans

def solve(budget):
    ans = cache[budget]
    if ans != -1:
        return ans

    ans = 0
    for d in dishes:
        if budget < d[0]: continue
        ans = max(ans, solve(budget - d[0]) + d[1])

    cache[budget] = ans
    return ans

for _ in range(int(input())):
    N, M = map(int, input().split())
    M //= 100
    dishes = []

    for _ in range(N):
        dishes_info = input().split()
        # dishes[i][0]: 가격, dishes[i][1]: 선호도
        dishes.append((int(dishes_info[0]) // 100, int(dishes_info[1])))

    sorted_dishes = sorted(dishes, key=lambda x: -x[1] / x[0])
    cache = []
    print(greedy() + solve(M))