백준 11052 - 카드 구매하기

문제 설명

 

 

=> DP 문제입니다. 

 

=> 카드 i개를 구매할 때의 최대 비용을 생각해야 합니다.

=> D[i] : 카드 i개 구매하는 최대 비용

 

 

=>카드 i개를 구매하는 방법의 가짓수

 

• 카드 1개 들어있는 카드팩 구매, 카드 i - 1개 구매

• 카드 2개 들어있는 카드팩 구매, 카드 i - 2개 구매

• ....

• ....

• ....

• 카드 i 개 들어있는 카드팩 구매, 카드 0개 구매

 

 

 

 

 

이를 나타내면

 

 

• P[1] + D[i-1] 

 

 

위와 같이 표현할 수 있습니다.

이를 코드로 표현하면 

 

 

for(int i=1; i<=N; i++ )
    {
        for( int j=1; j <= i; j++)
        {
            D[i] =  max(D[i], D[i - j] + P[j]);
        }
    }
    

 

위와 같은 코드가 됩니다.

 

 

 

 

 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>


using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    cin >> N;
    
    vector<int> P(N+1);
    vector<int> D(N+1);
    
    int tmp;
    for(int i=1; i<= N; i++)
    {
        cin >> tmp;
        P[i] = tmp;
    }
    
    
    for(int i=1; i<=N; i++ )
    {
        for( int j=1; j <= i; j++)
        {
            D[i] =  max(D[i], D[i - j] + P[j]);
        }
    }
    
    cout <<D[N] <<'\n';
    
    
}

 

 

 

 

 

실행 화면 1

 

실행 화면 2