[백준 BOJ][DP] 11052 붕어빵 판매하기

11052_붕어빵 판매하기

 

링크

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

 

풀이

 

 

붕어빵을 N개 팔아서 얻을 수 있는 최대 이익을 DP[N]이라고 정의하고, 붕어빵 N개 팔 때의 가격을 P[N]이라고 정의하겠습니다.

그리고 DP는 모두 0으로 초기화 하겠습니다.

 

 

위의

1 5 6 7 의 예제로 설명하겠습니다.

 

붕어빵 1개를 팔아야 한다면 D[1-1] + P[1] 하나뿐입니다.

참고로 DP[1-1] + P[1]은 1-1개 팔 때 최대 이익 + 1개 팔 때의 가격입니다.

 

붕어빵 2개를 팔아야 한다면

DP[2-1] + P[1]

DP[2-2] + P[2]

중에 큰 값이 DP[2]가 될 것입니다.

 

DP[2-1] + P[1]은 1+1=2고, DP[2-2] + P[2]는 0+5=5입니다.

DP[2] = DP[2-2] + P[2]가 되겠네요.

 

붕어빵 3개를 팔아야 한다면

DP[3-1] + P[1]

DP[3-2] + P[2]

DP[3-3] + P[3]

중에 큰 값이 DP[3]이 될 것입니다.

 

DP[3-1] + P[1]은 5+1=6, DP[3-2] + P[2]는 1+5=6, DP[3-3] + P[3]은 0+6=6입니다.

어쨌든 DP[3]=6이네요.

 

 

마지막입니다.

붕어빵 4개를 팔아야 한다면

DP[4-1] + P[1]

DP[4-2] + P[2]

DP[4-3] + P[3]

DP[4-4] + P[4]

중에 큰 값이 DP[4]가 될 것입니다.

 

DP[4-1] + P[1]은 6+1=7, DP[4-2] + P[2]는 5+5=10, DP[4-3] + P[3]은 1+6=7, DP[4-4] + P[4]는 0+7=7입니다.

DP[4], 즉 4개의 붕어빵을 팔 때, 최대로 얻을 수 있는 이득은 10이네요.

 

 

일반화 하겠습니다.

i는 1~n까지, j는 1~j까지 for문을 돌려줍니다.

DP[i] = MAX(DP[i-j] + P[j], DP[i]); 을 사용해서 DP[i]를 구해줍니다.

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

//11052_붕어빵 판매하기 #include <iostream> using namespace std;   int DP[1001], P[1001];   int MAX(int a, int b){     return a > b ? a : b; }   int main(){     int n;     int i, j;       cin >> n;       for (i = 1; i <= n; ++i)         cin >> P[i];       for (i = 1; i <= n; ++i){         for (j = 1; j <= i; ++j){             DP[i] = MAX(DP[i-j] + P[j], DP[i]);         }     }       cout << DP[n] << endl;       return 0; } Colored by Color Scripter

cs