BOJ 11047 동전0

이 문제는 설탕배달보다 더 간단한 그리디 문제이다. 왜냐하면 이 문제는, "만약 해당 값이 조건을 충족 못 시킬 시, 돌아와서 - 한다 " 라는게 없다. 

 

처음 풀었을 때는 동전 값 받으면서, k보다 작거나 같으면서 가장 큰 값을 구해서 k/max , k%max로 하고, 그 후 다시 배열을 돌면서 while문으로 동전 개수를 증가시키고, k값을 감소시켰다. (복잡..)

 

처음 제출한 알고리즘은 이러하다.

#include <iostream>
using namespace std;
int main(void) {
	int n, k;
	cin >> n;
	cin >> k;
	int coin[10];
	int max=0; //max와 max인덱스를 구한다
	int index = 0;
	for (int i = 0; i < n; i++) {
		cin >> coin[i];
		if (coin[i] > max && coin[i] <= k) { max = coin[i], index = i; };
	}

	int x = k / max; //max를 쓸 수 있는 개수 
	k = k % max; //max를 쓰고 남은 값
	for (int i = index-1; i >= 0; i--) { //for문 횟수 줄이려고 max인덱스 받았었음
		if (coin[i] > k) continue;  //k보다 크면 conitune
		else {
			while (coin[i] <= k) { //k보다  작거나 같을 동안
				x++; 
				k -= coin[i];
			}
			if (k == 0) break;
		}
	}
	cout << x;
}

하지만 더 간단하게 풀 수 있었다.

 

int main(void) {
	int n, k;
	cin >> n;
	cin >> k;
	int coin[10];
	for (int i = 0; i < n; i++) {
		cin >> coin[i];};

	int x = 0;
	for (int i = n-1; i >= 0; i--) {
		if (coin[i] > k) continue;
		x += k / coin[i];
		k = k % coin[i];
	}
	cout << x;
}

 

근데 알고리즘 시간은 동일했다.

아무튼 두번째 제출한게 더 직관적이다