[백준 11052] 카드 구매하기, C++

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

11052번: 카드 구매하기

 본 문제는 DP문제로 입력된 N개의 카드를 각지 위해 지불해야하는 금액의 최댓값을 출력하는 것이다. Bottom-up 방식으로 풀었다.

1. 카드 개수 및 카드 가격 입력
2. d[n] = max(d[n], d[n-j] + a[j])의 형태의 점화식 정의
   
   • 이때, d는 개수당 최대금액을 저장하는 배열, a는 카드의 가격을 나타내는 배열이다.
3. 카드를 1개 살때 최대값부터 4개를 살때 최대값까지 계산

Top-down

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int d[1001] = {0};
int a[1001];
 
int cal(int n) {
    if (n == 0) return 0;
    else if (d[n] > 0) return d[n];
    for (int i = 1; i <= n; i++) {
        d[n] = max(d[n], cal(n-i) + a[i]);
    }
    return d[n];
}
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
   }
    int ans = cal(n);
    printf("%d", ans);
}
 

 

Bottom-up

#include <cstdio>
 
using namespace std;
 
int a[1001];
int d[1001];
 
int cal(int a, int b) {
    if (a > b) return a;
    else return b;
}
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    d[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            d[i] = cal(d[i], d[i-j] + a[j]);
        }
    }
    printf("%d", d[n]);
    return 0;
}