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

1. 문제이해

11047번: 동전 0 (acmicpc.net)

11047번: 동전 0

 

동전의 개수(N)와, 만들어야하는 가치의 합(K), 그리고 각 동전의 값이 주어진다.

동전들은 매우 많고, 동전들을 가지고 K원을 만들려고 할 때,

필요한 동전의 개수를 출력하는 프로그램을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

동전들의 개수와 각 동전들의 값을 입력받아 K원을 만들면 된다.

그리고, 이 경우 필요한 동전의 총 개수를 출력하는 것이 목표이다.

아래 예제들을 통해 자세히 살펴보자. (예제가 기니, 2번은 건너뛰어도 좋다.)

---

<예제 1>

동전의 개수는 10개이고, 4200원을 만드는 것이 목표이다.

주어진 동전들의 값은 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000 이다.

 

첫 번째로, 만들려고 하는 금액은 4200원이므로, 4200원보다 큰 값들의 동전은 모두 필요가 없다.

따라서, 필요한 동전은 1, 5, 10, 50, 100, 500, 1000 뿐이다.

 

두 번째로, 값이 큰 동전부터 세어줘야 동전개수의 최솟값을 구할 수 있으므로,

(1000원으로 4000원을 만드는데는 4개의 동전이 필요하지만,

1원으로 4000원을 만드는데는 4000개의 동전이 필요하게 된다.)

1000원부터 값을 세어보면,

4200 - 1000 = 3200

3200 - 1000 = 2200

2200 - 1000 = 1200

1200 - 1000 = 200

따라서, 1000원은 4개가 필요하게 된다.

(200원은 1000원보다 작은 값이므로 빼줄수가 없다.)

 

이후 남은 값인 200원보다 큰 값들은 첫 번째 법칙에 의해 지워주고,

남은 값들인 1, 5, 10, 50, 100 중 큰 값인 100원으로 다시 위와 같은 과정을 반복하면,

200 - 100 =100

100 - 100 = 0

 

따라서, 100원짜리 동전 2개가 추가로 필요하게 되어,

6개의 동전으로 4200원을 만들 수 있게 된다.

 

 

<예제 2>

동전의 개수는 10개이고, 4790원을 만드는 것이 목표이다.

주어진 동전들의 값은 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000 이다.

 

예제 1과 동일한 방법으로, 만들려고 하는 금액인 4790원보다 큰 값들의 동전은 모두 필요가 없다.

따라서, 필요한 동전은 1, 5, 10, 50, 100, 500, 1000 뿐이다.

 

두 번째도 동일하게, 값이 큰 동전부터 세어줘야 동전개수의 최솟값을 구할 수 있으므로,

1000원부터 값을 세어보면,

4790 - 1000 = 3790

3790 - 1000 = 2790

2790 - 1000 = 1790

1790 - 1000 = 790

따라서, 1000원은 4개가 필요하게 된다.

 

이후 남은 값인 790원보다 큰 값들은 첫 번째 법칙에 의해 지워주고,

남은 값들인 1, 5, 10, 50, 100, 500 중 큰 값인 500원으로 다시 위와 같은 과정을 반복하면,

790 - 500 =290

500원짜리 동전은 1개가 필요하게 된다.

 

490원보다 작은 값들 중 제일 큰 값인 100원으로 다시 위와 같은 과정을 반복하면,

290 - 100 = 190

190 - 100 = 90

100원짜리 동전은 2개가 필요하게 된다.

 

90원보다 작은 값들 중 제일 큰 값인 50원으로 다시 위와 같은 과정을 반복하면,

90 - 50 = 40

50원짜리 동전은 1개가 필요하게 된다.

 

40원보다 작은 값들 중 제일 큰 값인 10원으로 다시 위와 같은 과정을 반복하면,

40 - 10 = 30

30 - 10 = 20

20 - 10 = 10

10 - 10 = 0

10원짜리 동전은 4개가 필요하게 된다.

 

따라서, 1000원짜리 동전 4개, 500원짜리 동전 1개, 100원짜리 동전 2개,

50원짜리 동전 1개, 10원짜리 동전 4개가 필요하게 되어,

총 12개의 동전이 필요하게 된다.

---

설명이 길어보이지만 원리는 비교적 간단하다.

 

1. 만들고자하는 값보다 큰 값의 동전은 제외한다.

2. 값이 큰 동전부터 만들고자 하는 값에서 빼준다.

3. 동전의 값보다 만들고자 하는 값이 작아지면, 위의 과정을 다시 반복한다.

 

위 3가지 원리를 코드에도 그대로 적용시켜보았다.

 

 

 

3. 소스코드

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

int main() {
	int N;	// 동전의 개수
	int K;	// 가치의 합
	int coin[10];	// 각 동전의 값
	int count = 0;	// 필요한 동전의 개수
	int index;	// 현재 가리키고 있는 동전의 값

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> coin[i];
	}

	sort(coin, coin + N);	// 동전의 값 정렬
	index = N - 1;

	while (K != 0) {	// K원이 만들어지면 while문 종료

		if (coin[index] > K) {	// K원보다 동전의 값이 더 크면
			index--;	// 다음 동전 값(더 작은 값) 확인 위해 index 값 감소
		}

		else {	// K원보다 동전의 값이 더 작으면
			K -= coin[index];	// 해당 값만큼 K원에서 빼주고
			count++;			// 필요한 코인의 개수 증가
		}
	}

	cout << count;

	return 0;
}

동전의 개수(N)와 만들려고 하는 값(K), 그리고 각 동전들의 값(coin[i])을 차례로 입력받는다.

동전들의 값은 큰 값부터 차례로 빼줘야 하기 때문에 정렬 후, 인덱스값을 N-1로 초기화한다. 

(인덱스는 현재 동전의 값을 가리키는 변수이다.)

 

K원이 0원이 될때까지, while문 안의 작업을 반복한다.

while문 안에서는 if문을 통해, 1. 만들려고 하는 값(K) 보다 큰 코인들을 제외시킨다.

이후, index 값을 하나씩 감소시켜주어, 더 작은 동전값을 확인한다.

 

K원보다 큰 코인들을 제외시키고, K원보다 작거나 같은 코인이라면,

2. 해당 코인값을 전체 K원에서 빼주고, 필요한 코인의 갯수를 증가시킨다.

 

이후, 다시 3. 현재 코인값보다 K값이 작아지면, 위의 과정을 K원이 0원이 될때까지 반복한다.

 

 

---

즐거운 추석연휴 보내고들 계신가요🥰

열심히 쉬려고 했지만.. 역시 시간이 나는데 아무것도 안하고 있는 것은

성미에 맞지 않는 것 같아서 코딩을 하는 중이다..

그래도 쉴땐 쉬어야 하는데..🤣🤣

언제 갑자기 쉬게 될지 모르니까.. 지금 할수 있을 때

열심히 해놓자는 마음이 더 큰것같기도 하다..ㅎㅎ