[baekjoon 11052] 카드 구매하기- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

이 문제는 비교적 빠르게 풀었다. 며칠 동안 dp만 잡고 있었더니 좀 익숙해지는 것 같기도 하고..

 

우선 카드의 개수는 그 숫자가 가지고 있는 인덱스이다.

10,15,20,30 -> 카드 한 장 사는데 10원, 카드 두 장 사는데 15원, 세 장은 20원, 네 장은 30원

 

따라서 처음 접근할 때는 결국 자연수들의 합으로 N을 만드는 경우의 수들을 구한 뒤에, 그 경우의 수를 인덱스 삼아서 max값을 찾으면 되겠다.라고 생각했는데 경우의 수가 너무 많다는 생각을 했다.

 

예를 들어 1장 카드 만들 때는 card[1] 밖에 없지만

2장은 card[1]+card[1], card[2]가 있고

3장은 1+1+1, 2+1, 3

4장은 1+1+1+1, 2+1+1, 2+2, 3+1, 4 등 점점 늘어난다.

 

이 모든 경우마다 카드의 금액을 계산하는 것은 무리라고 생각했고 이때 DP의 개념을 이용했다.

 

각 N마다 뽑을 수 있는 최대의 금액을 넣어놓으면 DP 배열로만 덧셈을 진행해주면 훨씬 경우의 수가 줄어들겠거니 생각했고

 

N = 1인 경우 DP[1] = card[1] (한 장 뽑는 것은 한 장 짜리 뽑는 경우의 수가 최대이다.)

N = 2인 경우 DP[2] = max(DP[1] * 2, card[2]) (두 장 뽑는 것은 N=1일 경우 최대 * 2와 두장짜리 카드 자체와 비교)

N = 3인 경우 DP[3] = max(DP[1]+DP[2], card[3]) (세 장 뽑는 것은 1+2 또는 3 만 비교해주면 된다)

->왜냐하면 이미 DP[1]과 DP[2]엔 해당되는 카드의 개수를 뽑는 최적의 해가 저장되어 있기 때문에 dp의 총합만 비교

 

따라서 이제 N이 커질수록 DP 배열끼리만 비교해주면 된다.

4인 경우 DP[4], DP[1]+DP[3], DP[2]+DP[2]

(DP[3]엔 이미 1+1+1, 1+2, 3 중에 최적인 경우가 저장되어 있다. 따라서 모든 경우의 수를 생각할 필요가 없다.)

 

마지막으로 만약 10이면 1+9, 2+8... 5+5까지 비교해주면 된다.

(1+2+3+4인 경우는?? 그 경우엔 1 + 9(를 만드는 최적의 경우의 수)에 저장되어 있을 수도, 2+8(를 만드는 최적의 경우의 수), 3+7, 4+6 등을 계산할 때 모두 고려된다.)

 

#include <iostream>
using namespace std;

int card[1001], DP[1001], N;

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> card[i];
		DP[i] = card[i];
	}
	DP[1] = card[1];
	DP[2] = max(card[1] * 2, card[2]);
	DP[3] = max(DP[3], DP[1] + DP[2]);
	for (int i = 4; i <= N; i++) {
		int f = i / 2;
		for (int j = 1; j <= f; j++) {
			DP[i] = max(DP[i], DP[j] + DP[i - j]);
		}
	}

	cout << DP[N];
}

입력받을 때 DP[i]에 card[i]를 넣어주었다. -> DP 배열은 N과 같은 카드 개수를 뽑는 비용으로 초기화.

 

int f = i/2 한 이유는 2+3이나 3+2이나 금액이 같기에 그냥 연산을 줄여주기 위해 해 주었다.