https://www.acmicpc.net/problem/11052
문제
> 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.
> PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다.
> 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.
전설카드
레드카드
오렌지카드
퍼플카드
블루카드
청록카드
그린카드
그레이카드
> 카드는 카드팩의 형태로만 구매할 수 있고,
카드팩의 종류는 카드 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과 같아야 한다.접근
dp를 사용한다.
N장을 뽑으려고 할 때 돈을 젤 많이 쓸 때를 dp(N)이라고 하면 일단 dp값의 초기로 각각 N장 들어있는 카드팩을 살 때로 잡는다.
이는 N이 3일 때, 3장팩, 2+1장 팩, 1+1+1장팩을 사는 3가지 경우중 3장팩을 사는 경우를 초기로 잡아준것이다.
이제 나머지 2+1, 1+1+1을 구해줘야한다.
N장에 대해서 초기로 N장팩을 잡았기 때문에 반복문으로 1부터 시작해서 N-1 + 1장팩을 살 경우, N-2 + 2장팩을 살경우 ...N-N/2 + N/2 장 팩을 살 경우까지 따져준다.
N/2이후는 어차피 반복 되는 경우기 때문에 따져주지 않는다.
N이 2라면 2, 1+1인 두 경우를 본다. 여기서 둘 중 더 큰게 dp(2)로 오고
N이 3이면 3, 2+1, 1+1+1을 봐야한다.
근데 이는 다시보면 2+1과 (1+1)+1로 dp(2)에 1팩짜리의 가격을 더한 값이 된다. dp(2)에서 이미 dp(2)와 dp(1)+dp(1) 중 누가 더 큰지 가렸기 때문에 위의 수식으로 해주면 다 따져지는 것이다.
문제해결
> N장의 카드를 뽑아야하므로 N을 입력받고, 각 카드 별 최대 비용을 위한 dp벡터, 그리고 카드팩의 가격을 각 dp의 초기값을 잡는다.
> 1장 팩은 경우가 1개이므로 2장 팩부터 따져준다.
> dp(2)와 dp(2-1) + dp(1)중 더 큰걸 dp(2)값으로 가진다. 이를 N까지 반복한다.
> N장에 대한 최대 비용인 dp(N)을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
vector<int> dp(N + 1);
for (int i = 1; i <= N; i++) cin >> dp[i];
for (int i = 2; i <= N; i++)
{
for (int j = 1; j <= i/2; j++)
{
dp[i] = max(dp[i], dp[i - j] + dp[j]);
}
}
cout << dp[N] << '\n';
}
후기
가능한 경우를 일단 나열하고 흐름을 멀리봤다 가까이 보면서 식을 어떻게 다른식으로 생각하면 되는지를 잘 찾아내야 한다.
