문제링크
https://www.acmicpc.net/problem/11052
문제
카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.
민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.
예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.
P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.
마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.
카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.
입력
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
출력
첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.
조건
- 시간 제한 : 1s
- 메모리 제한 : 256MB
해설
주어진 값들로 조건에 맞게 최댓값을 만들면 된다. 다이나믹 프로그래밍을 이용해 K번째 원소에서 선택할 수 있는 최선의 방법을 만들고, K+1번째에서 역시 최선의 방법을 골라 선택한다.
풀이
i번째 카드팩에서의 경우에 대해 살펴보자. 이전 카드팩들을 조합하여 살 수 있는 경우보다 i번째 카드팩을 선택했을때의 금액이 더 크다면 i번째 카드팩의 금액을 선택해야한다. 그러나, 이전 카드팩의 경우가 더 크다면 이전 카드팩을 조합하여 금액을 최대로 만들어야 한다.
만약 8까지의 카드팩이 있고, 최선의 방법이 1+2+5를 선택하는 것이라면, 1+2를 택하는 방법이 3을 택하는 방법보다 큰 금액을 갖는다는 것을 의미한다. 만약 3에서 선택할 수 있는 최댓값을 3에 이미 대입했다면 3에는 1+2의 값이 담겨있을 것이고, 3+5의 방법으로 카드팩을 선택하여도 1+2+5를 선택하는 방법과 같은 결과를 갖는다. 따라서, card[N] = card[K] + card[N-K]와 같다. 이를 이용해 i번째 카드팩에 대한 코드를 세우면 아래와 같다.
// i번째 카드팩의 가격을 card[i]에 담기
cin >> card[i];
for(int k = 1; k <= i; k++) {
// card[i]에 최선의 방법(최대금액)을 담기
// 최선의 방법은 k를 증가시키며 모든 경우의 수를 따져보고 결정한다
card[i] = (card[i] > card[k]+card[i-k])? card[i]:card[k]+card[i-k];
}N개의 카드팩에 위 코드를 반복시키면 최대금액을 쉽게 구할 수 있다.
코멘트
그냥 짜봤는데 왜 되지....? 하는걸 경험했다. ㅋㅋㅋ
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> card(N+1);
for(int i = 1; i <= N; i++) {
cin >> card[i];
for(int k = 1; k <= i; k++) {
card[i] = (card[i] > card[k]+card[i-k])? card[i]:card[k]+card[i-k];
}
}
cout << card[N];
return 0;
}
Uploaded by Notion2Tistory v1.1.0