C++ / 백준 / 11047 / 동전 0

문제

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

11047번: 동전 0

문제풀이

문제를 제대로 보지 않아 불필요한 for문을 썼다.

처음에는 동전이 1, 8, 10원이 있을 때, K가 16이라면 8+8=2의 경우를 생각해서 for문을 써서 모든 경우를 탐색하게 했다.

하지만 A[i]는 A[i-1]의 배수이기 때문에 위의 예시는 나올 수 없다.

	for (idx = N - 1; idx >= 0; --idx) {
		int won = K;
		int won_cnt = 0;
		int temp = idx;
		while (won > 0 && temp >= 0) {
			if (won >= coin[temp]) {
				won_cnt += (won / coin[temp]);
				won %= coin[temp];
			}
			else temp--;
			if (won_cnt >= won_min) break;
		}
		if (won == 0) won_min = min(won_min, won_cnt);
	}

현재 돈을 가장 큰 단위부터 나눈 몫을 won_cnt에 더하고, 남은 돈으로 다시 while문을 돌린다.

현재 가진 돈이 0원 이상이고 나누지 않은 동전의 단위가 남았을 때 while문을 돌린다.

마지막에 남은 돈이 0원 보다 많을 때만 최솟값을 계산할 수 있도록 했는데 이 문제에서 모든 입력은 남은 돈이 항상 0이게 나오는 것 같다. 따라서 마지막 if문은 필요 없다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	int N = 0, K = 0;
	cin >> N >> K;

	vector<int>coin(N + 1, 0);

	int idx = 0;
	for (idx = 0; idx < N; ++idx)
		cin >> coin[idx];

	int won_min = 100000000;

	for (idx = N - 1; idx >= 0; --idx) {
		int won = K;
		int won_cnt = 0;
		int temp = idx;
		while (won > 0 && temp >= 0) {
			if (won >= coin[temp]) {
				won_cnt += (won / coin[temp]);
				won %= coin[temp];
			}
			else temp--;
			if (won_cnt >= won_min) break;
		}
		if (won == 0) won_min = min(won_min, won_cnt);
	}
	cout << won_min;
}