회전초밥 SUSHI

문제:  https://algospot.com/judge/problem/read/SUSHI

문제

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

초밥	계란	연어	장어	대뱃살	스테이크	후라이드 치킨
가격	2500	3000	4000	5000	10000	15000
선호도	7	9	10	12	20	1

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

코드 ( C ++ ) 종만북 참조

#include <iostream>

#include <algorithm>

using namespace std;

int n, m;

int price[21], priority[21];

const int MAX = 201;

int cache[MAX];

// 최대 만족도의 합을 반환한다.

int sushi2() {

int ret = 0;

cache[0] = 0;

for (int budget = 1; budget <= m; ++budget) {

int cand = 0;

for (int i = 0; i < n; ++i)

if (budget >= price[i])

cand = max(cand, cache[(budget - price[i]) % 201] + priority[i]);

cache[budget % 201] = cand;

ret = max(ret, cand);

}

return ret;

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(0);

int C;

cin >> C;

while (C--)

{

int temp;

cin >> n >> temp;

m = temp / 100;

for (int i = 0; i < n; ++i)

{

int num1;

cin >> num1 >>  priority[i];

price[i] = num1/100;

}

int ans = sushi2();

cout << ans << "\n";

}

return 0;

}