(cpp) Baekjoon 11047번 문제 ‘동전0’ - 그리디

01 Oct 2022 on Programming Languages

Baekjoon 11047번 문제 ‘동전0’ - 그리디

---

문제

풀이

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
using namespace std;

int n,k;
int a[11];

int main() {
	//동전의 종류 n ...ㅈㄴ많음
	//각 동전의 가치 a1,a2... (서로 배수관계)
	//가치의 합 K
	//필요한 동전의 최소갯수?
	//1.큰 가치로 나눔
	//2.나머지를 그 다음 순위의 가치로 나눔
	//3.나머지 0될때까지 반복

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


	int ans = 0;
	for (int i = n - 1; i >= 0; i--) {

		ans = ans + k / a[i];
		k = k % a[i];
	}
	cout << ans;

}