[백준] 11047번: 동전 0 [C++]

 

알고리즘 분류: 그리디 알고리즘

문제 링크: https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

 

【 풀이 】

 

그리디 알고리즘을 활용하는 그리디 기초 문제이다.

동전 거스름돈은 항상 가장 큰 금액의 동전부터 거슬러 주는 것이 최적해이기 때문에

n개의 동전들을 배열에 저장해 주고 배열의 맨 뒤에서부터 계산해 주면 된다.

 

 

【 코드 】

#include<iostream>
using namespace std;

int a[1000001];
int main(void)
{
	int cnt = 0;
	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++)
		cin >> a[i];

	for (int i = n - 1; i >= 0; i--)
	{
		if (k % a[i] != k)
		{
			cnt += k / a[i];
			k %= a[i];
		}
	}
	cout << cnt;
	return 0;
}