[백준] 4781번 사탕 가게

문제 주소 : https://www.acmicpc.net/problem/4781

---

1. Approach

 

(1) 다이나믹 프로그래밍으로 접근한다. 

 

-> 이유는 사탕의 종류가 최대 5000개, 소유한 돈 100원, 사탕이 개당 0.01원 이라면

 

i) 현재 사탕을 선택하는 경우

 

ii) 현재 노드를 선택하지 않는 경우

 

-> 1번 사탕을 선택하고 다음 차례에 1번 사탕을 다시 선택할 수 있으므로, 중복을 포함한 5000개의 사탕을 총 10000번   선택하게 되면 시간초과가 발생하게 된다.

 

(2) DP 배열 정의

 

-> DP[money]  : 돈 money로 살 수 있는 사탕의 최대 칼로리

 

 

(3) 돈을 소수점 둘째자리까지 받으므로, 100을 곱해서 int형으로 바꾼다음 문제를 풀어나간다.

 

2. Source Code

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAX 5001
#define INF 987654321
using namespace std;
/*
	문제 설명

	1. 돈 m을 가지고 주어진 사탕으로 가장 많은 칼로리의 사탕을 사야한다.

	풀이 방법

	1. dp[candy_num][money] : candy_number 까지 남은 돈 money로 살 수 있는 최대 칼로리를 정의하고 싶다.
	2. money가 float이고 소수점 둘째자리까지 가능하므로 100을 곱해서 int로 만들자
	3. 각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다.
*/
int n; float temp_money;
int money;
vector<pair<int, int>> cal_price;
int dp[10001];

int solution(int m)
{
	int& result = dp[m];
	if (result != -1) return result;

	result = 0;
	for (int i = 0; i < n; i++)
	{
		if (m + cal_price[i].second <= money)
			result = max(result, solution(m + cal_price[i].second) + cal_price[i].first);
	}
	
	return result;
}


int main()
{
	while (1)
	{
		cal_price.clear();
		cin >> n >> temp_money;
		if (n == 0 && temp_money == 0.00) break;
		money = temp_money * 100;
		int c; float temp_p; int p;
		memset(dp, -1, sizeof(dp));
		for (int i = 0; i < n; i++)
		{
			cin >> c >> temp_p;
			p = temp_p * 100;
			cal_price.push_back(make_pair(c, p));
		}
		cout << solution(0) << endl;
	}


	return 0;
}