100win10 2019. 8. 16. 17:34

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


문제

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

초밥계란연어장어대뱃살스테이크후라이드 치킨
가격25003000400050001000015000
선호도791012201

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


코드 ( 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;

}