코테/Greedy
[C/C++] 나동빈 거스름돈, Greedy
상똥
2023. 2. 2. 12:02
문제
거슬러줘야 할 돈이 N원일 때, 거스름돈으로 사용할 동전 500원, 100원, 50원 그리고 10원을 조합한 동전의 최소 개수를 구하라. 단, N은 항상 10의 배수이다. |
코드
#include<stdio.h>
#include <iostream>
using namespace std;
int coin[4] = { 500,100,50,10 };
int main() {
int N, sum = 0;
cin >> N;
for (int i = 0; i < 4; i++) {
sum += N / coin[i];
N %= coin[i];
}
cout << sum;
}
풀이
1. 동전의 최소 개수를 구해야 하므로, 단위가 가장 큰 동전(500원)부터 내림차순으로 배열 coin 에 저장한다.
2. for문을 통해 N을 coin[i]로 나눈 몫만큼 sum에 더한 후
3. N을 coin[i]로 나눈 나머지 값으로 초기화한다.