문제
https://www.acmicpc.net/problem/11047
금액이 다양한 화폐가 있다고 했을 때, 특정 금액을 구성하기 위해 필요한 가장 최소 화폐개수를 구해보자.
예) 1000원은 100원짜리 10개도 되지만, 500원짜리 1개도 되고, 1원짜리 1개도 된다.
접근 방식
금액을 화폐단위로 나눈 몫이 그 개수이므로, 이것을 계속 더해나간다. 단 가장 큰 단위의 화폐단위부터 적용해야하므로, 오름차순 정렬되어있으므로, 가장 뒤에있는 단위부터 차례대로 나눠서 몫을 더한다.
그리고, 다음 단계에서는 이전에 카운트된 금액만큼 제외하고 다시 나누어야 하므로 나머지 연산자를 통해서 다음에 사용할 금액을 구한다.
ex)
100원, 500원, 1000원이 있다고 했을 때, 2300원을 가지고 생각해보자.
1) 2300 / 1000 = 2
2) 300 / 500원 = 0
3) 300 / 100원 = 3
2300원에서 2000원은 제외하고, 300원부터 출발해야하므로 이럴때 나머지 연산을 사용한다.
(풀이)
| #include <stdio.h> #include <stdlib.h> int main(int argc, char* argv[]) { int N, K; int value[10]; int i = 0; int answer = 0; fscanf(stdin, "%d %d", &N, &K); for (i = 0; i < N; i++) { fscanf(stdin, "%d", value+i); } for (i=(N-1); i >= 0; i--) { answer += K / value[i]; K %= value[i]; } printf("%d\n", answer); return 0; } |
회고
없음.