알고리즘(C++) / 백준 11047 : 동전 0

11047

www.acmicpc.net/problem/11047

11047번: 동전 0

 

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

코드

//11047 동전 0
#include <iostream>
using namespace std;

int main() {
	int N, K;
	int A[10]; //동전의 가치

	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	} //A1 = 1, Ai는 A(i-1)의 배수이다. 

	int count = 0;
	for (int i = N - 1; i >= 0; i--) {
		if (A[i] <= K) {
			count = count + K / A[i];
			K = K % A[i];
		}
		if (K == 0)
			break;
	}

	cout << count << endl;

	return 0;
}

 

결과

 

설명

K원을 만드는데 필요한 동전 개수의 최솟값을 출력하는 것이 문제이다.

A배열에 오름차순으로 수들을 입력받아 저장할 수 있다.

반복문을 이용하여 N번째 배열부터 1까지 K보다 처음으로 작은 값을 찾는다. 그 때 count에 K를 A[i]로 나눈 몫을 더해주고 K에는 나머지를 저장해준다. 여기서 count는 최솟값을 저장하는 변수이다.

K가 0일 때는 최솟값을 찾았으므로 반복문을 빠져나와 count를 출력할 수 있다.

 

고찰

처음 도전한 그리디 문제였다.

이번 문제를 풀면서 수많은 에러가 발생하였다. 처음에는 시간 초과가 발생하였고, 다음엔 런타임 에러가 발생하였다.

처음 문제를 풀었을 때 코드

//11047 동전 0
#include <iostream>
using namespace std;

int main() {
	int N, K;
	int A[10]; //동전의 가치

	cin >> N >> K;


	for (int i = 0; i < N; i++) {
		cin >> A[i];
	} //A1 = 1, Ai는 A(i-1)의 배수이다. 

	int sum = K;
	int i = 9;
	int num = 0;
	while (sum != 0) {
		if (A[i - 1] <= sum && sum <= A[i]) {
			sum -= A[i - 1];
			num++;
		}
		else
			i--;
	}


	cout << num << endl;
	return 0;
}

다음과 같이 코드를 구현하였다. 

결론적으로 출력은 같았지만 시간 초과였다.

사실 어떤 부분에서 틀린지 잘 모르겠지만,,,,, 좀 더 공부해 봐야할 것 같다.

그리디 문제를 좀 더 파악해 나아가야 할 것 같다.