2. 문제 요약: 가지고 있는 붕어빵의 개수가 주어지고, 붕어빵을 묶음으로 팔 때 얼마를 받게 되는지가 주어진다. 붕어빵이 모두 팔린다는 가정하에, 어떻게 세트 메뉴를 구성해야 수익이 극대화되는가?
3. 문제 접근법
작은 문제로 하나씩 나눈다.
붕어빵 1개를 팔 때 극대화되는 수익
붕어빵 2개를 팔 때 극대화되는 수익
붕어빵 n개를 팔 때 극대화되는 수익
임의의 수 k에 대하여 k개의 붕어빵을 팔아야 하고, k-1개 붕어빵에 대해서는 이미 답을 알고 있다고 하자.
그렇다면,
붕어빵 1개 세트를 추가로 파는 경우, 붕어빵 2개 세트를 추가로 파는 경우, ... 붕어빵 k개 세트를 추가로 파는 경우 중 최대값을 찾는다.
이때, k-1에서 k개로 넘어오면서 추가된 붕어빵은 1개이므로, 붕어빵 2개를 추가로 팔려고 하면 2개를 추가로 팔되, 이전까지 판매한 수익은 k-1개 기준이 아니라 k-2개 기준이 되어야 한다.
이것은 3개, 4개 ...k개 통째로 세트로 파는 경우 등에도 그대로 적용된다.
4. C코드
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
30
|
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
int N;
scanf("%d", &N);
int *S = (int*)malloc(sizeof(int) * (N + 1));
int *dp = (int*)malloc(sizeof(int) * (N + 1));
S[0] = 0;
for(int i = 1; i <= N; i++)
{
scanf("%d", &S[i]);
dp[i] = 0;
}
dp[1] = S[1];
for(int i = 2; i <= N; i++)
{
dp[i] += S[i] + max(dp[i - 2], dp[i - 3] + S[i - 1]);
}
printf("%d\n", dp[N]);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기