[백준 알고리즘] 11052번 붕어빵 판매하기

문제 

강남역에서 붕어빵 장사를 하고 있는 해빈이는 지금 붕어빵이 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<=1000) 두번째줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

풀이

이거 뭔가 행렬의 곱 최소화시키는 문제랑 비슷한거 같다 

붕어빵이 i개 일때 pi까지 모든 세트의 수가 들어있을텐데 f(i, n)로 만들어서 i개의 붕어빵을 팔때 세트 n을 사용하는 경우를 식으로 만

붕어빵 1개를 팔때는 p[1]가 최대수익이고 붕어빵 2개일때는 f(1)+p[1]과 p[2]중에서 큰 수익을 고르게 된다 붕어빵이 3개일때는 붕어빵2개 팔때 최대이익+p[1]과 p[3] 중에서 큰 수익을 고르게된다

f(1) = p[1]

f(2) = max(f(1)+p[1], p[2])

f(3) = max(f(2)+p[1], f(1)+p[2],, p[3])

f(4) = max(f(3)+p[1], f(2)+p[2], f(1)+p[3], p[4])

f(5) = max(f(4)+p[1], f(3)+p[2] , f(2)+p[3], f(1)+p[4], p[5])

f(n) = max(f(n-1)+p[1], f(n-2)+p[2], ..., f(1)+p[n-1], p[n])

코드

dp[1]=p[1];

for(i=2; i<=n; i++)

{

result = p[i];

for(j=1; j<=i; j++)

{

if(result < dp[i-j]+p[j])

result = dp[i-j]+p[j];

}

dp[i]=result;

}