SOLUTION INFO
C++ · main.cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N; cin >> N;
int two = 0, five = 0;
while(5 * (five + 1) <= N) ++ five;
N -= five * 5;
while(2 * (two + 1) <= N) ++ two;
N -= two * 2;
while(N > 0) {
if(five == 0) return cout << -1, 0;
-- five;
two += 3;
N -= 6;
}
cout << two + five;
return 0;
}
SOLUTION DESCRIPTION
풀이 설명
아래 풀이 중 첫 번째 풀이다. 이 문제는 `n`원을 `2`원 짜리 동전 `x`개와 `5`원 짜리 동전 `y`개로 어떻게 나누고 그 중 `x + y`의 값 중 최솟값을 구할 수 있을지 물어보는 문제이다. 동전을 최소 개수로 사용해야하므로 가장 큰 단위인 5원 동전을 먼저 사용하고 나머지 2원을 사용하는 것이 최솟값이라는 것을 쉽게 알 수 있다. 하지만, 여기서 `8`원 같은 경우는 `5`원을 하나도 쓰지 않고 `2` 원 4개를 써야 가능하다. 이걸 어떻게 구할 수 있을지 고민을 해보자. 일단, 두 가지 방법으로 풀 수 있을 것 같다. 먼저, `5`원을 최대한 사용하고 나머지를 `2` 원을 쓴 이후에 거스름돈이 `1` 원 남는다면 사용한 `5` 원을 다시 회수해 총 `6` 원을 `2` 원짜리 3개로 주면 된다. 두 번째로는, 식으로 풀 수 있다. 이를 식으로 적는다면 `2x + 5y = n` 을 만족하는 음이 아닌 정수 `x` 와 `y` 쌍들을 구하고 이 중에서 `x + y` 값 중 최솟값을 구하면 된다. 여기서 계산을 하는데 시간안에 돌아가는지 확인해야한다. 여기서 `n`의 최댓값은 10만이므로 `y`를 0부터 `n / 5` 까지 정수 하나씩 대입하면서 `x`와 `y` 쌍을 구할 수 있다. 여기서 `n / 5` 는 2만이므로 시간복잡도는 `O(2만)` 인 것을 알 수 있다. 여기서 `y`를 기준으로 계산을 했기 때문에 `O(2만)`이 나왔는데 `x` 기준으로 잡는다면 `O(5만)` 시간복잡도가 된다. 이 결과를 봤을 떄 `y`를 기준으로 계산하는 것이 더 효율적인 것을 알 수 있다. - 시간복잡도: `O(N)` (두 가지 풀이 시간복잡도는 같다.)