5) 백준 11052 - 카드 구매하기

<문제>

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

요즘 다른 공부를 좀 하고 있어서 코딩은 잘 안하는거 같다... ㅠㅠㅠ 틈틈히 해야하는데 ㅠ

 

 

<코드>

#include <iostream>

using namespace std;

int memoi[1001] = {0, };
int cards[1001] = {0, };

int dp(int x) {
	memoi[1] = cards[1];
	if(x == 1) {
		return memoi[1];
	}
	
	for(int i = 2; i <= x; i++) {
		for(int j = 0; j < i; j++){
			memoi[i] = max((memoi[j] + cards[i-j]), memoi[i]);
		}
	}
	
	return memoi[x];
}


int main(void) {
	int n;
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		cin >> cards[i];
	}
	
	cout << dp(n);
	
	return 0;	
}

방법은 다음과 같다.

메모이제이션을 사용할 것인데 1인 경우에만 먼저 저장해둔다.

만약, 카드 개수가 1이라면 바로 빠져나오게 한다.

 

N이 2이상인 경우부터 생각해보자면 카드 갯수가 i까지 만을 생각했을 때 금액의 최댓값을 memoi라는 배열에 저장한다.

 

문제에 나와있는 예시로 예를 들어보자.

P1 = 1
P2 = 5
P3 = 6
P4 = 7

카드를 1개만 구매하는 경우의 종류는 P1 하나만 구매하는 경우밖에 없다. 따라서 memoi[1] = card[1]이 된다. (참고로 card 배열에는 index가 카드의 갯수이고, 해당 index에는 카드팩의 가격이 적혀있다.)

 

카드를 2개 구매하는 경우의 종류는 P1을 두개 사거나 P2를 하나만 사면 된다. 이 말은 즉 memoi[1]에서 구매한 카드팩과 P1 카드팩을 추가로 구매를 하거나, P2카드팩을 하나만 사는 경우가 된다. 두 경우중 가장 큰 경우를 memoi[2]에 넣는다.

 

카드를 3개 구매하는 경우의 종류는 P1을 세개 사거나, P1하나와 P2 하나를 사거나 P3 하나만 사는 경우다. 그러나 우리는 이미 카드팩 한개를 사는 경우와, 카드팩 두개를 사는 경우에서 가격의 최댓값을 memoi[1]과 memoi[2]에 저장해두었다. 따라서 memoi[1]과 P2카드팩을 사는 경우, memoi[2]와 P1카드팩을 사는 경우, P3 카드팩의 가격중에 더 큰값을 memoi[3]에 넣어주면 된다.

 

마지막으로 카드를 4개 구매하는 경우의 종류는 P1을 네개 사거나, P1두개와 P2하나를 사는 경우, P1한개와 P3하나를 사는 경우, P2두개를 사는 경우, 마지막으로 P4하나를 사는 경우가 있다. 그런데 여기서도 우리는 카드팩을 한개, 두개 그리고 세개를 사는 경우의 최댓값을 memoi[1], memoi[2], memoi[3]에 저장해두었다. 카드3개를 구매하는 경우와 똑같이생각해 본다면 memoi[1]과 P3카드팩, memoi[2]와 P2카드팩, memoi[3]과 P1카드팩 그리고 P4카드팩 따로 구매하는 경우 중 금액이 최댓값인 경우를 확인하면 된다.

 

결론은, 카드를 n개 구매한다고 하면 memoi[i]와 P(n-i)카드팩(i는 1부터 n-1까지)을 구매하는 경우들과 Pn 중에서 가장 큰 값을 찾아내면 된다. 

 

끝!

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

이런 느낌의 DP는 풀수 있을거 같은데 워낙 문제 스타일이 다양해서 다른건 공부가 더 필요할듯 하다..ㅠㅠㅠㅠ