[BOJ 11047] 백준 동전0 풀이 - C++

사용언어 :  C++

 

 

 

문제풀이

 * stack 이용하기!

 

(1) 순서대로 동전 stack에 push하기

(오름차순이라 순서대로 push 가능)

(2) stack top이 k보다 작으면 top으로 사용할 수 있을만큼 answer에 더해주고, k를 그만큼 감소시킨다(k를 top으로 나눈 나머지 값). 

(3) stack pop해준다. 

 

 

 

전체코드

 

#include <iostream>
using namespace std;
#include<stack>
int answer;
int main() {
	int n, k;
	cin >> n >> k;
	stack<int> s;
	int tmp;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		s.push(tmp);
	}
	while (k) {
		if (s.top() <= k) {
			answer += k / s.top();
			k %= s.top();
		}	
		s.pop();
	}

	cout << answer;
}

 

 

 

총평

실버2라서 겁먹었는데 생각보다 간단해서 당황했던 문제,,,,,, 

 

---

문제 출처

https://www.acmicpc.net/problem/11047

11047번: 동전 0