[BOJ 11052] 카드 구매하기

문제출저 : https://www.acmicpc.net/problem/11052

 

풀이 :

 

DP문제입니다.

동전문제와 거의 일치합니다.

메모이 제이션을 할 때 현재 cache에 쌓여있는 값과 이 팩을 샀을때의 값을 비교하여 쌓아가면 됩니다.

 

#include<stdio.h>
 
int n,card[1001],cache[1001];
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)scanf("%d", &card[i]);
    for (int i = 1; i <= n; i++)for (int j = i; j <= n; j++)cache[j] = cache[j-i]+card[i]>cache[j]?cache[j-i]+card[i]:cache[j];
    printf("%d", cache[n]);
}