마법 물약 제조
골드 III의견: 0
연금술사 루나는 마법 가마솥을 갖고 있다. 가마솥의 용량은 정확히 \(C\)이며, 재료를 정확히 \(C\)만큼 채워야만 물약을 완성할 수 있다.
\(N\)종류의 재료가 있고, 각 재료는 무한히 사용할 수 있다. 재료 \(i\)는 용량 \(w_i\)를 차지하고 가치 \(v_i\)를 가진다.
가마솥을 정확히 \(C\)만큼 채울 때 달성할 수 있는 최대 가치 합을 구하여라. 채울 수 없다면 \(-1\)을 출력한다.
- \(1 \le N \le 100\)
- \(0 \le C \le 10\,000\)
- \(1 \le w_i \le C\) (단, \(C > 0\)일 때)
- \(1 \le v_i \le 500\)
첫째 줄에 재료의 종류 수 \(N\)과 가마솥 용량 \(C\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 재료 \(i\)의 용량 \(w_i\)와 가치 \(v_i\)가 공백으로 구분되어 주어진다.
가마솥을 정확히 \(C\)만큼 채울 수 있을 때 최대 가치 합을 출력한다. 채울 수 없다면 \(-1\)을 출력한다.
3 10
2 5
3 8
5 14
28
가마솥 용량 \(10\)을 정확히 채워야 한다. 재료 B(용량 \(3\), 가치 \(8\))를 두 번, 재료 A(용량 \(2\), 가치 \(5\))를 두 번 넣으면 \(3+3+2+2=10\), 가치 \(8+8+5+5=26\)이다. 재료 C를 두 번 넣으면 \(5+5=10\), 가치 \(28\)이다. 재료 B 세 번 + 오버플로우 불가 → 최선은 재료 C 두 번: \(28\).
2 4
3 10
5 15
-1
재료 용량이 \(3\)과 \(5\)뿐이므로 합이 \(4\)가 되는 조합이 없다. \(-1\)을 출력한다.
riseoj 작성
출처 Original
평가 및 의견
마법 물약 제조
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 물약 제조