은행원인 동수는 지폐를 동전으로 교환하는 손님들의 편의를 위해 최소 동전수로 교환해 주려고 한다. 즉, 500원, 100원, 10원 동전 단위가 사용될 때 1,000원에 대한 최소 동전수는 500원 2개, 즉 2다. N개의 동전 단위와 거스름돈 W가 주어질 때, 주어진 거스름돈을 거슬러 주는 최소 동전 수를 구하는 프로그램을 작성하시오. 단, 각 동전 단위의 개수는 무한대다. 예를 들어, 4개의 동전 단위 50원, 12원, 5원, 1원이 주어질 때 거스름돈 15원의 최소 동전 수는 3이다. 즉, 5원 3개가 거스름돈 15원의 가장 작은 동전 수다.

실행 파일의 이름은 문제 코드와 동일하다. 실행 시간은 2초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 동전 단위의 개수 N(1<=N<=1000)이 주어진다. 두 번째 줄에 N개의 동전 단위가 공백을 사이에 두고 오름차순으로 주어진다. 각 동전의 금액은 10,000 이하다. 세 번째 줄에 거스름돈 W(1<=W<=1000000)가 주어진다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄부터 최소 동전수를 출력한다.

입력과 출력의 예 1

입력 (INPUT.TXT)

출력 (OUTPUT.TXT)

입력과 출력의 예 2

입력 (INPUT.TXT)

출력 (OUTPUT.TXT)

// Dynamic Program

// 최소 동전 교환해 주는 방법

// 동전단위 예시: 50원, 12원, 5원 1원 일때

// 거스름돈: 15원 일때

// 동전이 4원, 3원 ,2원 1원 있을때는

// 최소동전 교환 공식= 거스름돈-동전단위+1

// 동전 2원 거슬러주며면 2-2원+1=1 즉 2원짜리 1개

// 15-50+1=-34 거스름돈이 15원이므로 50원짜리 동전은 불필요함

// 거스름돈 15원 일때 5원짜리 3개 주면됨

#include <stdio.h>

int mm[1000000]={0}; //min_money, 거스름돈 최소동전수

int N; // 동전 갯수

int am[1000]={0}; //arr_money, 동전단위 나열

int cm; //change_money, 거스름돈

int main()

{

int i;

int p,min1; //p: 거스름돈 p원

freopen("input.txt","r",stdin);

freopen("output.txt","w",stdout);

scanf("%d",&N); //동전 갯수 불러옴(4개)

for(i=1; i<=N; i++){

scanf("%d",&am[i]); // 나열된 동전 불러옴(1 5 12 50)

}

scanf("%d",&cm); // 거스름돈 불러옴(15원)

//동적계획법: 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을

//이용하여 효율적으로 값을 구하는 알고리즘 설계 기법

mm[0]=0;

for(p=1;p<=cm;p++){ //거스름돈 p,

min1=9999999;

for(i=1;i<=N;i++) // 동전갯수 N=> 4

{

if((p-am[i]>=0)&&(((mm[p-am[i]])+1) < min1))

//거스름돈-동전단위+1 이 0보다 크고 9999999 보다 작으면

{

min1=(mm[p-am[i]])+1;

//최소동전= 거스름돈-동전단위+1

}

}

mm[p]=min1; //거스름돈 최소동전수

}

printf("\n%d",mm[cm]);

return 0;

}

​

​

=========================================

// 최소동전 교환 Greedy 알고리즘(탐욕적 알고리즘)

// 동전교환 문제: 50원, 12원, 5원 1원 있을 때 15원 거스름돈 계산문제

#include <iostream>

using namespace std;

int main(){

int n, result=0;

cin >> n;

result=result+n/50;

n%=50;

result=result+n/12;

n%=12;

result=result+n/5;

n%=5;

result=result+n/1;

n%=1;

cout << result;

return 0;

}

<출력결과>

4 로 3이 나와야하나 오류로 다이나믹 알고리즘으로 해결해야함.

아니면 순서를 바꿔야하는 오류가 생김