동전0 | 백준 11047

#include <iostream>
using namespace std;

int main() {

 int i, n, k, sum=0, coin[10];
 cin >> n >> k;
 
 for(i=0; i< n; i++)
  cin >> coin[i];
  
 for(i--; i>=0; i--)
 {
  if(k>=coin[i])
  {
   int quoat = k/coin[i];
          k -= quoat*coin[i];
   sum+=quoat;
  }
 }
 
 printf("%d", sum);

 return 0;
}

이 문제는 n개의 동전을 가지고 k 원을 만들기 위해 최소한의 동전 개수를 구하는 문제이다. 역시나 간단한데, 가장 빠르게 풀기 위해서는 큰 수부터 접근하는 것이 좋을 것이다.
친절하게도 오름차순 정렬이기 때문에, 뒤의 인덱스부터 접근한다.

만들어야 할 k가 해당 값 coin[i]보다 크다면 그걸 나누어 몫을 계산하고(quoat) 이 몫을 sum에 더하며, 이 값만큼을 k에 빼서 연산을 반복하는 방식이다.

첫 번째 for문이 끝나면서 i는 n이 되므로, n-1부터 시작할 수 있도록 두 번째 for문에서 i--를 초기 값으로 넣어 주었다.

• Twitter
• Facebook
• Google
• Tumblr
• Pinterest