붕어빵 판매하기 / DP, 점화식 세우기

붕어빵 판매하기

분류  : DP

난이도  : 2 / 5

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

평

간단한 다이나믹 프로그래밍 문제이다. 점화식을 세우는 것이 관건이다.

문제를 간략이 표현하자면, 남은 붕어빵을 1개, 2개, 3개 ... N개씩 묶어 팔때, 가격이 다른데, 남은 붕어빵의 갯수를 최대이익으로 팔면, 그때의 최대이익은 얼마인가를 찾는 문제이다.

막무가내로 생각하면 어렵다. 단순히 INPUT의 값을 해당 INDEX로 나누어 마리당 가격을 계산해서 높은 것 부터 다 팔고... 남은 것은 2순위로 팔고 ... 이런 식으로 계산하면 몹시나 어렵다.

점화식을 세워서 DP로 풀어야한다.

D[N]을 N마리를 팔 때, 최대이익이라고 하자. 그렇게 된다면

D[N]은 MAX( D[N-1] + A[1], D[N-2] + A[2], ... )이 된다.

N이 10이라면, 

9마리까지 팔렸을 때 최대이익에 1마리를 파는 이익과 

8마리까지 팔렸을 떄 최대이익에 2마리를 파는 이익과

....

1마리까지 팔렸을 떄 최대이익에 9마리를 파는 이익과

한번에 10마리를 파는 이익

을 비교해서 최대값을 고르면 되는 것이다.

수식으로 정리하면 

D[N] = MAX ( D[N], D[N-K] + A[K] )  ( K는 N보다 같거나 작은 자연수)

#include<iostream> #pragma warning(disable:4996) using namespace std; int N; int D[1001]; int A[1001]; int max(int a, int b) { return a > b ? a : b; } int main() { cin >> N; for (int i = 1; i <= N; ++i) cin >> A[i]; // 처음 한마리를 파는 이익은 A[1]이다. D[0] = 0; D[1] = A[1]; for (int i = 2; i <= N; ++i) { D[i] = D[i - 1] + A[1]; for (int k = 2; k <= i; ++k) { D[i] = max(D[i - k] + A[k], D[i]); } } cout << D[N] << endl; }