[다이나믹 프로그래밍] 붕어빵 판매하기

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

붕어빵 판매하기 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 12537 7217 5361 57.813% 문제 강남역에서 붕어빵 장사를 하고 있는 해빈이는 지금 붕어빵이 N개 남았다. 해빈이는 적절히 붕어빵 세트 메뉴를 구성해서 붕어빵을 팔아서 얻을 수 있는 수익을 최대로 만드려고 한다. 붕어빵 세트 메뉴는 붕어빵을 묶어서 파는 것을 의미하고, 세트 메뉴의 가격은 이미 정해져 있다. 붕어빵 i개로 이루어진 세트 메뉴의 가격은 Pi 원이다. 붕어빵이 4개 남아 있고, 1개 팔 때의 가격이 1, 2개는 5, 3개는 6, 4개는 7인 경우에 해빈이가 얻을 수 있는 최대 수익은 10원이다. 2개, 2개로 붕어빵을 팔면 되기 때문이다. 1개 팔 때의 가격이 5, 2개는 2, 3개는 8, 4개는 10 인 경우에는 20이 된다. 1개, 1개, 1개, 1개로 붕어빵을 팔면 되기 때문이다. 마지막으로, 1개 팔 때의 가격이 3, 2개는 5, 3개는 15, 4개는 16인 경우에는 정답은 18이다. 붕어빵을 3개, 1개로 팔면 되기 때문이다. 세트 메뉴의 가격이 주어졌을 때, 해빈이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 해빈이가 가지고 있는 붕어빵의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) 출력 해빈이가 얻을 수 있는 최대 수익을 출력한다. 예제 입력 1  4 1 5 6 7 예제 출력 1  10 예제 입력 2  5 10 9 8 7 6 예제 출력 2  50 예제 입력 3  10 1 1 2 3 5 8 13 21 34 55 예제 출력 3  55 예제 입력 4  10 5 10 11 12 13 30 35 40 45 47 예제 출력 4  50 예제 입력 5  4 5 2 8 10 예제 출력 5  20 예제 입력 6  4 3 5 15 16 예제 출력 6  18

[ 문제 풀이 ]

- D[N]을 붕어빵 N개를 팔았을 때 낼 수 있는 최대 수익으로 정한다.

- 점화식을 유도해본다.

* P[n] = 붕어빵 n개를 세트로 묶어 팔 때의 수익 

D[1] = P[1]

D[2] = max(D[1] + P[1], P[2])

D[3] = max(D[2] + P[1], D[1] + P[2], P[3])

D[4] = max(D[3] + P[1], D[2] + P[2], D[1] + P[3], P[4])

...

D[N] = max(D[N-1] + P[1]

                     ....

                D[0]    + P[N]     <- D[0] = 0으로 두면 반복문을 구현할 때 편하다.

[ 최종 구현(C++) ]

#include <stdio.h>
#define MAX_BREAD_COUNT 1002

int D[MAX_BREAD_COUNT] = { 0 };
int P[MAX_BREAD_COUNT] = { 0 };

int main(void)
{
	int N = 0;
	scanf("%d", &N);

	for (register int i = 1; i <= N; i++) scanf("%d", &P[i]);
	D[0] = 0; D[1] = P[1];

	for (register int i = 2; i <= N; i++)
	{
		int tempMaxPrice = 0;

		for (register int j = 1; j < i; j++)
			tempMaxPrice = tempMaxPrice > (D[i - j] + P[j]) ? tempMaxPrice : (D[i - j] + P[j]);

		D[i] = (P[i] > tempMaxPrice) ? P[i] : tempMaxPrice;
	}

	printf("%d\n", D[N]);

	return 0;
}