728x90
https://www.acmicpc.net/problem/14916
14916번: 거스름돈
첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.
www.acmicpc.net
2원, 5원을 사용해서 거스름돈을 줘야 하는데, 5원을 먼저 나누고 나머지를 2로 나누면 되는가? 아니다
N=13의 경우, 5원 2개 / 2원 1개 이렇게 하면 안 된다. 대신 5원 1개 / 2원 4개로 하면 된다.
즉, 5원이 0개 / 1개 / 2개 사용하는 경우를 모두 확인해봐야 최적의 해를 구할 수 있다.
그러므로 N을 5원으로 나눠서 5원을 최대로 많이 사용할 수 있는 경우를 u에 넣어주고
for문을 사용해서 최솟값을 구하면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, cnt=2147483647;
cin >> n;
int u = n / 5;
for(int i=0; i<=u; i++){ //5원을 0개부터 u개 사용하는 경우
int m = n, c = i;
m -= 5 * i;
c += m / 2;
m %= 2;
if(m == 0){
cnt = min(cnt, c);
}
}
if(cnt == 2147483647) cout << "-1\n";
else cout << cnt << '\n';
return 0;
}
728x90
'알고리즘 > 백준' 카테고리의 다른 글
[백준/c++] 1758번: 알바생 강호 (0) | 2022.07.12 |
---|---|
[백준/c++] 2217번: 로프 (0) | 2022.07.12 |
[백준/c++] 6550번: 부분 문자열 (0) | 2022.07.12 |
[백준/c++] 3135번: 라디오 (0) | 2022.07.12 |
[백준/c++] 19564번: 반복 (0) | 2022.07.11 |