[DP] 백준 문제 풀이 - 11052 카드 구매하기

👩🏻‍💻 문제링크

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

11052번: 카드 구매하기

 

✍️ 아이디어

1. 문제 이해

• 1장~N장이 들어있는 카드팩이 있는데 N장의 카드를 사기 위해 가장 많은 돈을 지불하는 방법을 구함

2. 처음 내 생각은 1장부터 n-1장까지 가장 많은 돈을 지불하는 경우를 전부 구하면 n장은 저 사이에서 2개를 더한 값과 같을거라 생각함

 

✍️소스코드

• 나의 코드 : 최댓값끼리 더하면 최댓값 나오지 않을까? 라는 반례가 안나와서 그냥 밀어붙임

#include <iostream>
using namespace std;
long long result[1001]; //카드 N개를 갖기위해 지불하는 최대 금액

int main()
{
	int card[1001];
	card[0]=0;
	int n; cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>card[i];
	}
	
	for(int i=1; i<=n; i++)
	{
		result[i]=card[i]; //처음으로 카드팩 하나를 사는것을 가정
		for(int j=0; j<=i; j++)
		{
			if(result[i]<result[i-j]+result[j]) // 최댓값끼리 더하면 최댓값 나오지 않을까?
			{
				result[i]=result[i-j]+result[j];
			}
		}
	}
	cout<<result[n]<<'\n';
}

 

• 다른 사람의 코드 : 이것이 더 이해가 잘됨

https://yabmoons.tistory.com/23

여기서는 i - j 개의 카드를 살때의 최대 금액과 j개가 들어있는 카드팩을 살때를 더해서 최댓값을 구하고 있다

ex) 카드 4개 살때의 최댓값

1. 카드 3개를 살 때의 최댓값 + 1번째 카드

2. 카드 2개를 살 때의 최댓값 + 2번째 카드

3. 카드 1개를 살 때의 최댓값 + 3번째 카드

4. 카드 0개를 살 때의 최댓값 + 4번째 카드

 

체감난이도	걸린시간	참고	사용 문법
중	30min	x	2차원 DP