[백준] 알고리즘 11047번 - 동전 0 문제

동전0문제

www.acmicpc.net/problem/11047

11047번: 동전 0

소스코드

#include <bits/stdc++.h>
using namespace std;
int arr[11];
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int n, k,ans=0;
   cin >> n >> k;
   for (int i = 0; i < n; i++)cin >> arr[i];
   for (int i = n - 1; i >= 0; i--) {
	   if (k/arr[i]) {
		   ans += k/arr[i];
		   k %= arr[i];
	   }
   }
   cout << ans;
}

해결방법

간단한 그리디 알고리즘입니다.

배열에 오름차순으로 저장된다고 하니 가장 끝에서부터 차례대로 k로 나눌 수 있는지 확인하여 카운트해주면 됩니다.