[BOJ] 백준 #11047. 동전 0 (C++)

🎨 문제

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

• 알고리즘 분류: 그리디 알고리즘
• 난이도: Silver 3

 

💬 풀이

벡터 v에 동전의 가치를 차례로 입력받고, 

 

반복 {

    cnt += K/v[i];

    K %= v[i];

}

 

 

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	//freopen("input.txt", "rt", stdin);
	int N, K;
	cin >> N >> K;
	vector<int> v(N);
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	for (int i = N - 1; i >= 0; i--) {
		if (K == 1) {
			cnt++;
			break;
		}
		if (cnt += K / v[i]) {
			K %= v[i];
		}
	}
	cout << cnt;

	return 0;
}