백준 1661 다솜이의 신발가게

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

1661번: 다솜이의 신발가게

 

풀이 

0. 핵심 아이디어

같은 할인률이면 물건의 가격이 낮은것을 사는것이 이득입니다.

그렇기에 물건들을 할인률 별로 묶고 오름차순으로 관리할 수 있습니다.

 

N이 최대 50밖에 안되기 때문에

(1퍼센트 사용) / (2퍼센트 사용) / (3퍼센트 사용) 갯수를 정해두고 브루트포스로 탐색해서

가장 낮은 가격이 되는 값을 구하면됩니다.

 

자세한것은 코드를 참고해주세요.

코드

 

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const int INF = 999999999999999;
const int Dic[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

////////////////////////////////////////////////////////////////////////

int N, P;
vector<int> items[4];
float ans = 0;
float Get(int a, int b, int c) //(1퍼센트 사용) / (2퍼센트 사용) / (3퍼센트 사용)
{
	if (items[1].size() < a)
		return P;
	if (items[2].size() < b)
		return P;
	if (items[3].size() < c)
		return P;

	float now = P;
	float sum = 0;
	for (int i = 0; i < a; i++)
	{
		now = now * 0.99f;
		sum += (float)items[1][i];
	}
	for (int i = 0; i < b; i++)
	{
		now = now * 0.98f;
		sum += (float)items[2][i];
	}
	for (int i = 0; i < c; i++)
	{
		now = now * 0.97f;
		sum += (float)items[3][i];
	}

	return now + sum;
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	//소수점 자리수 설정
	cout << fixed;
	cout.precision(12);

	std::cin >> N >> P;
	for (int i = 0; i < N; i++)
	{
		int a, b;
		std::cin >> a >> b;
		//할인률별로 모아준다
		items[b].push_back(a);
	}
	for (int i = 1; i <= 3; i++)
	{
		//할인률별로 묶인것을 정렬
		sort(items[i].begin(), items[i].end());
	}

	ans = P;
	for (int i = 0; i <= N; i++)
		for (int j = 0; i + j <= N; j++)
			for (int k = 0; i + j + k <= N; k++)
			{
				//(1퍼센트 사용) / (2퍼센트 사용) / (3퍼센트 사용) 갯수를 정해놓고 적용해본다.
				ans = min(ans, Get(i, j, k));
			}

	std::cout << ans << endl;

}