[C++/백준] 11052번: 카드 구매하기

문제 링크

11052번: 카드 구매하기

 

풀이

DP를 이용하는 문제

1. 점화식을 구한다.
   1. n이 4라고 하면 4개짜리 하나 사는 경우와 `,2,3개짜리를 섞어서 사는 여러 경우가 있을 것이다.
   2. dp의 i번째 인덱스는 i개를 살 때 최댓값을 지불하는 경우가 저장되어 있을 텐데, 이를 이용해 1개짜리 사는 최댓값과 3개짜리 사는 최댓값을 더한 경우, 2개짜리 살 때 최댓값을 두 번 지불하는 경우, 그냥 4개짜리 사는 경우들에서 최댓값을 구해준다.
   3. 정리하면 점화식은, dp[n] = max(dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n/2]+dp[n-n/2], dp[n](입력하면서 그냥 여기에 넣어줄거임))이 될 것이다.
2. 점화식을 이용해 코드를 짜는데, 같은 경우를 두 번 계산하지 않기 위해 i/2까지만 계산하도록 하였다.

 

코드

#include <iostream>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int dp[1001];
    for (int i = 1; i <= n; i++)
    {
        cin >> dp[i];
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i / 2; j++)
        {
            dp[i] = max(dp[i], dp[j] + dp[i - j]);
        }
    }
    cout << dp[n];
}