백준 11052: 붕어빵 판매하기

문제

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

해당 문제의 경우는 다이나믹 프로그래밍으로 생각하는 것이 가장 중요합니다.

저 또한 문제를 보았을때, 아직까지는 정확히 어떤것을 먼저 해야되고 어떠한 식으로 접근을 해야되는지 

감이 오질 않아 많이 힘든 부분도 있습니다. 하지만 언젠가는 익숙 하겠지요? 

<핵심> D[i]를 붕어빵 i개를 팔아 얻을 수 있는 최대 수익, P[i]는 붕어빵 i개로 이루어진 세트메뉴의 가격이라고 합시다.   총 i개의 붕어빵 중에서 1개를 P[1]에 판다면 남은 붕어빵의 개수는 i-1개이며 얻을 수 있는 최대 이익은 D[i-1] 입니다. →  총 수익 : P[1] + D[i-1] 총 i개의 붕어빵 중에서 2개를 P[2]에 판다면, 남은 붕어빵의 개수는 i-2개이며 얻을 수 있는 최대 이익은 D[i-2] 입니다. →  총 수익 : P[2] + D[i-2] 이렇게 쭉 나아가다 보면, 붕어빵 i-1개를 P[i-1]에 판다면, 남은 붕어빵의 개수는 1개이며 최대 이익은 D[1] →  총 수익 : P[i-1] + D[1] 붕어빵 i개를 P[i]에 판다면, 남은 붕어빵은 없으므로 이익은 D[0]입니다. →  총 수익 : P[i] + D[0]

D[i]로 만들어질 수 있는 수익의 경우는 i개 입니다. 이들을 비교하여 제일 높은 수익을 D[i]에 저장하면 됩니다.

코드

/*p는 정해진 가격, d는 붕어빵을 팔았을 때 최대 수익
 붕어빵 4개 팔때 최대수익 = 붕어빵 1개 묶음 섞어서 팔때 최대수익 + 붕어빵 3개 팔때 최대수익
                    = 붕어빵 2개 묶음 섞어서 팔때 최대수익 + 붕어빵 2개 팔때 최대수익
                    = 붕어빵 3개 묶음 섞어서 팔때 최대수익 + 붕어빵 1개 팔때 최대수익
                    = 붕어빵 4개 묶음 섞어서 팔때 최대수익 + 붕어빵 0개 팔때 최대수익*/
 
#include <iostream>
 
using namespace std;
 
int p[1001],d[1001];
 
int dp(int n){
    if(n == 0) return n;
    if(d[n] > 0) return d[n];
    for(int i=1; i<=n; i++){
        d[n] = max(d[n],dp(n-i)+p[i]);
    }
    return d[n];
}
int main(){
    int n;
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> p[i];
    cout << dp(n)<<"\n";
    return 0;
}