백준 4781번 사탕가게 C++

문제

www.acmicpc.net/problem/4781

4781번: 사탕 가게

코드1

#include<bits/stdc++.h>

using namespace std;

int n, c, dp[10001];
double m, p;
pair<int, int> candy[5001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (true)
	{
		memset(dp, 0, sizeof(dp));
		cin >> n >> m;
		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
		{
			cin >> c >> p;
			candy[i] = make_pair(c, (int)(p * 100 + 0.5));
		}

		int money = (int)(m * 100 + 0.5);
		for (int i = 0; i < n; i++)
		{
			for (int j = candy[i].second; j <= money; j++)
			{
				dp[j] = max(dp[j], dp[j - candy[i].second] + candy[i].first);
			}
		}
		cout << dp[money] << "\n";
	}

	return 0;
}

 

코드2

#include<bits/stdc++.h>

using namespace std;

int n, c, dp[10001];
double m, p;
pair<int, int> candy[5001];

int go(int cash)
{
	int& result = dp[cash];
	if (result != -1)
		return result;
    
    result = 0;
	for (int i = 0; i < n; i++)
	{
		if (cash - candy[i].second >= 0)
		{
			result = max(result, go(cash - candy[i].second) + candy[i].first);
		}	
	}
	return result;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (true)
	{
		memset(dp, -1, sizeof(dp));
		cin >> n >> m;
		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
		{
			cin >> c >> p;
			candy[i] = make_pair(c, (int)(p * 100 + 0.5));
		}

		cout << go((int)(m * 100 + 0.5)) << "\n";
	}

	return 0;
}