[백준][DP] 카드 구매하기

1. 문제 주소

11052번: 카드 구매하기

2. 문제

점화식을 세우기 위해 n=2일 때부터 차례대로 구해보았다. 구매하려고 하는 카드의 개수가 4개이고 p={1, 5, 6, 7} 일 때 

n=1---p[1]

n=2---max(p[2], p[1]+p[2-1])

n=3---max(p[3], p[1]+p[3-1], p[2]+p[3-2])

n=4---max(p[4], p[1]+p[4-1], p[2]+p[4-2],p[3]+p[4-3])

과 같이 구할 수 있다.

 

3. 소스 코드

1. Bottom-up

#include <iostream>
#include <algorithm>
using namespace std;
int p[1001];
int dn[1001];
int main(void)
{
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }
 
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dn[i] = max(dn[i], p[j] + dn[i - j]);
        }
    }
 
    cout << dn[n] << '\n';
    return 0;
}

 

2. Top-down

#include <iostream>
#include <algorithm>
using namespace std;
int p[1001];
int dn[1001];
 
int topdown(int n)
{
    if (n == 0)
        return 0;
    if (dn[n]) return dn[n];
 
    int result = 0;
    for (int i = 1; i <= n; i++)
    {
        result = max(result, topdown(n - i) + p[i]);
    }
    return dn[n]=result;
 
}
int main(void)
{
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }
 
    cout << topdown(n) << '\n';
    return 0;
}