BOJ : 11052 붕어빵 판매하기

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

기초 DP문제입니다. 

여느 DP 문제가 그렇듯이 가장 작은 수부터 고려해 점차 큰 수일 때 경우를 고려하는 Bottom-Up 방식으로 풀면됩니다.

DP에서 가장 중요한 것은 메모이제이션 그리고 점화식이죠.

예를 들어, 첫 번째 테스트 입력을 보겠습니다.

4
1 5 6 7

먼저 붕어빵 개수 당 가격을 담고 있는 fish[4] 배열과 각 수의 팔았을 때 가장 큰 값을 가진 배열 sum[4]가 있다고 봅시다.

먼저 붕어빵 한개를 팔때 가장 비싸게 파는 sum[1] = fish[1]가 되겠죠.

그 다음 붕어빵 두개를 팔 때는 두개에 파는 가격 fish[2]와 한 개 값으로 두 개를 파는 경우(sum[1]+fish[1])가 나옵니다. 이 중에 큰 값이 sum[2]가 되겠죠.

다시 세 개를 팔 때를 보면, 세 개를 묶어서 팔 때 fish[3], 두개 묶어서 하나 더 얹었을 때 (sum[2]+fish[1]), 

한 개에 두개 묶음을 얹어서 팔았을 때 (sum[1]+fish[2])를 비교해서 큰 값이 sum[3]이 됩니다.

(sum 배열이 의미하는 것은 해당 개수의 붕어빵을 팔았을 때 최대값으로 판 가격이기 때문에 별다른 과정을 다시 거칠필요가 없습니다.)

이러한 방법으로 N까지 반복하게 됐을 때 점화식은 sum[N] = max(sum[N], sum[N-j]+ sum[j])가 되고, 최종적으로 N개를 팔았을 때 최대값이 나오게 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;

int N, fish[1001], sum[1001]={0,}, ans=0;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d",&fish[i]);
    sum[1] = fish[1];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=i;j++){
            sum[i] = max(sum[i], sum[i-j]+fish[j]);
        }
    }
    
    printf("%d\n",sum[N]);
}