동전 문제
문제
구사과국은 동전만 사용하고, 동전의 가치는 다음과 같다.
1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000 …
즉, 식으로 표현하면 K ≥ 0를 만족하는 모든 K에 대해서, 가치가 10K인 동전과 25×100K인 동전이 있는 것이다.
구사과국에 살고 있는 구사과는 초콜릿을 하나 구매해 5차원 세계로 이사가려고 한다.
초콜릿의 가격이 주어졌을때, 이를 구매하기 위해 필요한 동전 개수의 최솟값을 구해보자.
각 동전의 개수는 무한하고, 구매할 때는 정확하게 초콜릿의 가격만큼만 지불해야 한다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다.
가격의 1015보다 작거나 같은 자연수이다.
출력
총 T개의 줄에 각각의 테스트 케이스의 필요한 동전의 개수를 출력한다.
풀이
유명한 그리디 문제인 동전 문제를 변형한 문제다.
우선 그리디로 동전 문제를 해결하려면 모든 동전들이 배수 관계여야한다는 조건이 필요하다.
하지만 현재는 1000, 2500 처럼 배수가 아닌 동전 금액이 섞여있다.
동전들을 나열하면 1, 10, 25, 100, 1000, 2500… 25가 곱해지는 동전은 100단위로 나온다.
이들을 배열에 저장하면 v[i]에서 i%3==2 일 때가 해당 동전이라는 것이다.
그리디하게 K를 지우면서 i%3==2 동전 차례에 앞의 자리를 보면 75이상, 50이상, 25이상, 25미만일 것이다.
우선 75일 때는 25 동전 2개로 지우는 것이 이득이고,
50 이상일 때는 25원을 2, 1, 0개 쓰는 것, 25 이상일 때는 1, 0개 쓰는 것 중 뭐가 더 이득인지 확인한다.
그렇게 각각의 케이스를 계산해서 가장 최소로 쓰는 것을 선택해주면 된다.
나머지 과정은 이와 반복하면 그리디하게 해를 구할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#define ll long long
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
cin >> t;
vector<ll> v;
k=1;
for(int i=0;i<=15;i++){
v.push_back(k);
k*=10;
}
k=25;
for(int i=0;i<=6;i++){
v.push_back(k);
k*=100;
}
sort(v.rbegin(), v.rend());
while(t-->0){
ll ans=0;
cin >> n;
for(int i=0;i<v.size();i++){
if(i%3==2){ // 25짜리들
if(n>=3*v[i]){ // 75이상이면 일단 50을 빼는게 맞음
ans+=2;
n-=2*v[i];
}
if(n>=2*v[i]){
ll tmpn = n-2*v[i]; // 25*2 빼고 나머지 처리 방법
a=(tmpn%(v[i]*2/5))/(v[i]/25)+(tmpn/(v[i]*2/5))+2;
ll tmpn2 = n-v[i]; // 25 빼고 나머지 처리 방법
c=(tmpn2%(v[i]*2/5))/(v[i]/25)+(tmpn2/(v[i]*2/5))+1;
b=(n%(v[i]*2/5))/(v[i]/25)+(n/(v[i]*2/5)); //25 안빼고 처리 방법
ans+=min({a,b,c});
n%=(v[i]/25);
}
else if(n>=v[i]){
ll tmpn = n-v[i]; // 25 빼고 나머지 처리 방법
a=(tmpn%(v[i]*2/5))/(v[i]/25)+(tmpn/(v[i]*2/5))+1;
b=(n%(v[i]*2/5))/(v[i]/25)+(n/(v[i]*2/5)); //25 안빼고 처리 방법
ans+=min(a,b);
n%=(v[i]/25);
}
}
else if(n>=v[i]){
ans+=n/v[i];
n%=v[i];
}
}
cout << ans << '\n';
}
// 3000 에서 2500을 빼면 500, 5*100 but 3000을 1000*3으로 보면 더 빠름
// 배수일 때만 그리디가 성립이니까
return 0;
}