[BOJ/백준] 11047번 - 동전 0

단계별로 풀어보기 > 그리디 알고리즘 > [1단계] 11047번

 

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

11047번: 동전 0

 

문제 요약

1. 그리디 알고리즘을 사용하는 대표적인 동전 문제

 

입력 복사

예제 입력 1 >> 출력 : 6

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 입력 2 >> 출력 : 12

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

 

CODE

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,k;
	cin >> n >> k;
	
	vector<int> v(n);

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

 

문제 풀이

- 화폐 가치가 큰 동전부터 차례로 선택하는 대표적인 그리디 알고리즘 풀이 문제.

- 복잡하게 생각해, 구태여 조건을 덧붙일 필요가 없었다...

 

참고 URL : https://salon.tistory.com/50

[C++][Competitive Programmer's Handbook] 그리디 알고리즘(1) - 동전 문제와 주의 사항