BOJ 백준온라인져지 11052 붕어빵 판매하기 풀이

문제 설명

1. 붕어빵 N 개로 최대 수익을 내면 된다.

풀이

1. P[i] 에는 붕어빵 i 개로 이루어진 세트의 가격이다.

2. dp[i] 는 붕어빵 i 개를 팔 때의 최대 수익이다.

3. dp[i] = max(dp[i], P[i] + dp[i - j]) 를 하면 된다. (3 개를 산다고 하면, (1, 1, 1), (2, 1) 을 비교하면 됨 (처음에 3개짜리를 넣어주면)

4. i 개를 판매할 때의 최대 수익 + P[i - j] 를 순서대로 갱신해주면

5. 1 -> 5 -> 6 -> 10

6. 10 -> 20 -> 30 -> 40 -> 50

7. 1 -> 2 -> 3 -> 4 -> 5 -> 8 -> 13 -> 21 -> 34 -> 55

코드

문제

강남역에서 붕어빵 장사를 하고 있는 해빈이는 지금 붕어빵이 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