[백준 11052] 붕어빵 판매하기

글에 개요

백준 알고리즘 11052번 "붕어빵 판매하기" 문제입니다.

이 문제는 DP(동적 계획법)을 활용하는 문제로 '1,2,3의 조합으로 나타내는 방법의 수' 뒤로 연습해보면 좋은 문제입니다.

역시 손으로 어느 정도의 규칙이 발견된 후에 점화식을 세우는 것이 좋은 방법인 것 같습니다.

아마 동적 계획법에 사용되는 점화식의 활용에 익숙해지고, 이후 재귀함수로 구현할 때 Top-down, Bottom-up 방식해 질 때까지 최대한 꾸준히 풀어볼 생각입니다.

[백준 11052] 붕어빵 판매하기: https://www.acmicpc.net/problem/11052

참고할 글

1. [백준 9095] 1, 2, 3 더하기 : http://brenden.tistory.com/29
2. [백준 10942] 팰린드롬? : http://brenden.tistory.com/27

핵심 내용

1. D[i] = i를 '붕어빵 i개를 팔아서 얻을 수 있는 최대 수익'
2. D[i] =max(D[i], D[i-j] + inputAry[j])

• 붕어빵 1개를 inputAry[1]에 팔기 -> 남은 붕어빵의 수는 i-1개 ▶ inputAry[1] + D[i-1]
• 붕어빵 2개를 inputAry[2]에 팔기 -> 남은 붕어빵의 수는 i-1개 ▶ inputAry[2] + D[i-2]
• 붕어빵 i-1개를 inputAry[i-1]에 팔기 -> 남은 붕어빵의 수는 i-1개 ▶ inputAry[i-1] + D[1]
• 붕어빵 i개를 팔 때는 ▶ D[i] = inputAry[j] + D[i-j] (1 <= j <= i)

해결 방법

1. 계산하기 편하게 index를 1부터 시작하게 코드를 작성한다.
2. 점화식을 바탕으로 코드를 작성한다.
3. 17 line 이 핵심이 된다.

해결한 코드

백준 내용 참고

붕어빵 판매하기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	10784	6206	4616	57.816%

문제

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