앳코더90 - 016 - Minimum Coins（★3）

https://atcoder.jp/contests/typical90/tasks/typical90_p

016 - Minimum Coins（★3）

 

A,B,C엔 동전을 0개 이상 사용하여 정확히 N엔 지불할 수 있을 때 동전의 개수중 가능한 최소 값을 구하여라.

제한 조건에 최대 9999개의 동전으로 정확히 N엔을 지불 가능하다라는 조건이 있는데, 이는 어떤 상황에서도 답이 존재한다는 의미이다.

 

ax + by + cz = N 이 성립하는가에 대한 부정방정식을 구하는 문제 같은데, a, b를 10000*10000 브루트포싱하고 나머지를 MOD값으로 계산해보면 1억 안에 답이 나올 것 같다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

ll N;
ll A, B, C;

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

	cin >> N;

	cin >> A >> B >> C;

	ll ans = INF;

	for (int i = 0;i < 10000;i++)
	{
		for (int j = 0;j < 10000;j++)
		{
			ll sum = A * i + B * j;
			if (sum > N)
				continue;
			ll left = N - sum;
			if (left % C == 0)
			{
				ans = min(ans, i + j + left / C);
			}
		}
	}

	cout << ans;

	return 0;
}