백준 11052번 - 붕어빵 판매하기

문제

강남역에서 붕어빵 장사를 하고 있는 해빈이는 지금 붕어빵이 N개 남았다.

해빈이는 적절히 붕어빵 세트 메뉴를 구성해서 붕어빵을 팔아서 얻을 수 있는 수익을 최대로 만드려고 한다. 붕어빵 세트 메뉴는 붕어빵을 묶어서 파는 것을 의미하고, 세트 메뉴의 가격은 이미 정해져 있다.

붕어빵 i개로 이루어진 세트 메뉴의 가격은 P_i 원이다.

붕어빵이 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)

둘째 줄에는 P_i가 P₁부터 P_N까지 순서대로 주어진다. (1 ≤ P_i ≤ 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

다이나믹 프로그래밍 문제라고 친구에게 받았지만 앞서 풀었던 문제들과 느낌이 달라서 당황스러웠다.

생각한 과정은 처음에 n 개당 얼마라는 가격이 정해져 있는데,

만약 2개를 파는 가격이 2개 가격보다 1개씩 두 개 파는 경우가 더 비싼 경우, 해당 숫자는 필요없게 된다.

P2의 존재가 의미 없어지고 P1 + P1이 P2의 가격을 대체하게 된다. 이를 MaxPrice[개수]로 별도 저장한다.

그런 식으로 쭉 각 개수에 대한 최대값을 기록하다보면 

MaxPrice[n]의 값을 구하기 편해진다. MaxPrice[n] = MaxPrice[n-i] + MaxPrice[i]( 0<= i <= n/2)가 된다.

3개 이상을 더해서 MaxPrice[n]을 구할 수 있지 않나 생각할 수 있는데 3개 이상의 항이 있을 때, 모든 항을 더해야 n의 개수와 같아지기 때문에 모두 MaxPrice가 존재한다. 따라서 두개의 항 밖에 존재하지 않는다.

#include <iostream>
#include <stdio.h>
using namespace std;
int price[1001] = {0};
int maxprice[1001] = {0};
int checkMaxPrice(int n)
{
      if(n == 1)
      {
          maxprice[n] = price[n];
          return maxprice[n];
      }
    else if(maxprice[n] != 0)
    {
        return maxprice[n];
    }
    else
    {
        int max = price[n];
        for(int i = 1; i<= n/2;++i)
        {
        	if(max < checkMaxPrice(i) + checkMaxPrice(n-i))
        		max = checkMaxPrice(i) + checkMaxPrice(n-i);
        }
        return maxprice[n] = max;
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i = 1; i<=n;++i)
    {
        cin>>price[i];
    } 
    int max = checkMaxPrice(n);
    cout << max;
    return 0;
}