[BEAKJOON] 11052_붕어빵 판매하기_C언어

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

풀이

2662번 기업투자를 푸는데...왠지 붕어빵과 비슷한 느낌이나서 다시 풀어보았다. 기업투자는 조만간 올리겠다!!

붕어빵을 어떻게 묶어 팔아야 제일 비싸게 팔 수 있느냐를 구하는 문제이다...DP문제는 글로 설명하기가 어렵다.

붕어빵이 n개 있으면 다음과 같이 생각할 수 있다.

1. 처음에는 0~n개 까지 붕어빵을 묶어 팔 수 있으며, 이때 i 개를 팔았다.

2. 전에 묶어판 붕어빠의 개수가 i개이면 지금 팔 수있는 붕어빵의 개수는 0~n-i이다. 이 경우의 수에서 j개를 팔았다.

3. 위의 1,2 경우에서 i+j개를 팔았으므로 지금 팔 수 있는 붕어빵의 개수는 0~n-i-a개이다.

이와 같은 방식으로 팔 수있는 경우의 수가 0개가 될 때 까지 계속해주며 모든 경우의 수에서 return되는 값들중 지금의 최소값과 return되어 온 값을 비교하여 최소값을 DP배열에 넣어주면 된다.

제출한 코드

#include <stdio.h>
int N, bread[1006], DP[1006];
 
int MAX(int a, int b)
{
    return a > b ? a : b;
}
 
int D(int n)
{
    if (n == 0)
        return 0;
    if (DP[n] != -1)
        return DP[n];
 
 
    for (int i = 1; i <= n; i++)
    {
        DP[n] = MAX(DP[n], D(n - i) + bread[i]);
    }
 
    return DP[n];
}
 
int main()
{
    scanf("%d",&N);
 
    for (int i = 0; i < 1005; i++)
    {
        DP[i] = -1;
    }
 
    for (int i = 1; i <= N; i++)
        scanf("%d", &bread[i]);
 
    printf("%d",D(N));
 
    return 0;
}