C언어 233제] NCP Nextop Lv.2 동전 0

출처 : 반크_반크 20년 백서

 

문제]

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1 
10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1 
6


예제 입력 2 
10 4790
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 2 
12


출처 : 백준_11047번

 

참고풀이]

#include <stdio.h>

int main()
{
   int N,K;
   int i,x;
   int A[10];
   int Sum;
   int cnt;

   scanf("%d%d",&N,&K);
   if((N>=1 && N<=10) && (K>=1 && K<=100000000))
   {
      for(i=0;i<10;i++) A[i]=0;
      for(i=1;i<=N;i++)//동전개수의 금액을 입력한다. 
         scanf("%d",&A[i-1]);

      Sum=cnt=0;
      x=K;
      while(1)
      {
         if(Sum>=K) break;
         for(i=N-1;i>=0;i--)
            if(A[i]<=x)
            {
               Sum+=A[i];
               x-=A[i];
               break;
            } 
         cnt++;
      }
      printf("%d",cnt);
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도