[BaekJoon][11052] 붕어빵 판매하기

BAEKJOON ONLINE JUDGE

11052 붕어빵 판매하기

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

DP

dp[n] = Max(i개 세트 가격 + 나머지 붕어빵 개수의 최대값)

1. top-down

#include <stdio.h>
 
#define Max(x, y)        (((x) > (y)) ? (x) : (y))
 
int n;
int cost[1001];
int dp[1001];
 
int solve(int num)
{
    int i;
 
    if (num == 0)    return 0;
    if (dp[num])        return dp[num];
    dp[num] = cost[num];
 
    for (i = 1; i <= num; i++) {
        dp[num] = Max(dp[num], cost[i] + solve(num - i));
    }
 
    return dp[num];
}
 
int main()
{
    int i;
 
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &cost[i]);
    }
 
    printf("%d\n", solve(n));
 
    return 0;
}

2. bottom-up

최적이 보장되기 떄문에 쉽게 bottom-up을 구현할 수 있다.

#include <stdio.h>
 
int n;
int cost[1001];
 
int main()
{
    int i, j;
 
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &cost[i]);
 
        for (j = 1; j <= i; j++) {
            if (cost[j] + cost[i - j] > cost[i])
                cost[i] = cost[j] + cost[i - j];
        }
    }
 
    printf("%d\n", cost[n]);
 
    return 0;
}