백준 문제 11052번 카드 구매하기 문제풀이 c++

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

문제해석

 

전형적인 dp문제인데

4

1 5 6 7

입력이 위 처럼 들어왔다고 가정해보자

 

카드 4장을 구매하는 경우는

1+1+1+1

1+1+5

1+6

7

5+5

이렇게 5가지가 존재하고 이 중 5+5가 가장 큰 값이 되므로 이것이 답이된다.

 

위의 5가지 경우를 식으로 나타내면

dp[4]=max({dp[3]+p[1],dp[2]+p[2],dp[1]+p[3],dp[0]+p[4]})가 되고 점화식을 일반화 하면

j의 범위 1<=j<=i에 대해서 dp[i]=max(dp[i],dp[i-j]+p[j]) 임을 찾을 수있고 코드로 작성하면 다음과 같다. 

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dp[1001];
int p[1001];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n; cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>p[i];
    }
    for(int i=1; i<=n; i++)
    {
        int mx=0;
        for(int j=1; j<=i; j++)
        {
            mx=max(mx,dp[i-j]+p[j]);
        }
        dp[i]=mx;
    }
    cout<<dp[n];
}