[백준/C++] 11047번 - 동전 0

 

문제

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

 

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

입력

 

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

 

출력

 

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

풀이

 

처음에는 동전이 배수로 주어지는 줄 모르고 경우의 수를 전부 구해보며 가지치기를 했다.

 

그런데 시간초과가 나길래 빠진 조건이나 가지치기를 더 하려고 문제를 읽어보니 A_i 번째 동전은 A_i-1 번째 동전의 배수였다.

 

그래서 단순하게 그냥 큰 동전부터 사용하도록 코드를 짰다.

 

이후에 더 생각해보니 큰 값으로 나누었을 때 몫이 1보다 클 경우 cnt에 몫을 더하고 나머지를 다시 남은 동전들로 계산하는 방법도 가능했다. (배수라 가능한 방법)

 

 

Code

 

 

 

#include<iostream>
using namespace std;

int N, K;
int money[10] = { 0, };
int greedy(int cnt, int money_value) {
	for (int i = N-1; i >=0; i--) {
		while (true) {
			if (money_value + money[i] > K) {
				break;
			}
			money_value += money[i];
			cnt += 1;
			if (money_value == K) {
				return cnt;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> K;
	int value;
	for (int i = 0; i < N; i++) {
		cin >> value;
		money[i] = value;
	}
	cout<<greedy(0, 0);
}

 

 

 

Code2

 

 

 

#include<iostream>
using namespace std;
// 배수이므로 나눗셈의 몫과 나머지를 이용
#include<iostream>
using namespace std;

int N, K;
int money[10] = { 0, };

int main() {
	int cnt=0;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> K;
	int value;
	for (int i = 0; i < N; i++) {
		cin >> value;
		money[i] = value;
	}
	for (int i = N - 1; i >= 0; i--) {
		cnt += K / money[i];
		K %= money[i];
	}
	cout << cnt;
}

 

 

 

---