[Baekjoon]11052.카드 구매하기(DP)

Baekjoon

#11052. 카드 구매하기

http://www.acmicpc.net/problem/11052

---

예전에는 붕어빵 판매하기 문제였는데 카드 구매하기 문제로 바뀐 것 같다. 문제를 읽어보니 내용만 다르고 문제에서 물어보는 것은 같은 것이었다. 카드 N개를 구매할 때 가장 비싸게 구매할 경우 가격 총합을 구하는 문제이다. 붕어빵 문제에서는 붕어빵 N개를 판매할때 최대 수익을 구하는 문제였다. 결국은 같은 말이다. 문제를 풀기 위해서 배열 d를 정의한다. 

d[n] : 카드 n개를 구매할 때 최대 가격

예전에 백준 알고리즘 인강을 들었을때 풀었던 방법을 참고했다. 1개를 살 때, 2개를 살 때, ..., n개를 살 때 각각 가격이 p[n]으로 다르다. 구매해야하는 총 카드의 개수가 n개이므로 먼저 1개를 p[1] 가격에 사고 나머지 n-1개를 최대가격으로 사는 방법, 즉 d[n-1]을 더하면 카드 n개를 구매할 수 있다. 똑같은 방법으로 먼저 2개를 p[2] 가격에 사고 나머지 n-2개를 최대가격으로 사는방법, d[n-2]를 더하면 카드 n개를 구매하게 된다. 

위 과정을 점화식으로 나타내면 

$$\mathbf{d[n]=max(p[i]+d[n-i]), (1\leq i\leq n)} $$

코드로 구현하면 다음과 같다.

		
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= i; j++) {
		d[i] = Math.max(p[j] + d[i - j], d[i]);
		}
	}

<전체코드>