[c/c++] 백준 11047 (Silver 4)

🔨 문제

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

<요약>
준규가 가지고 있는 동전은 총 N종류이고,동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

🔨 해결방법

1. 입력 조건 확인

- 무조건 n의 첫번째는 1이므로 1이 아니면 다시 입력받도록 설정
- 또 n번째의 숫자는 n-1번째의 배수이어야 하므로 배수가 아니면 다시 입력받도록 설정(나머지 연산자를 사용했다.)

2. while(n>1)문 이용하여 카운트 확인

조건은 k의 값이 money배열보다 큰 경우, money배열 사이에 위치한 경우(ex. k = 4200일 때 money[4]=1000, money[5] = 5000), 그렇지 않은 경우로 나눠줬다. 조건문에 한 번씩 걸릴 때마다 n--로 증감연산자를 사용하여 입력받은 모든 money 배열의 값을 비교해줬다.

근데 내가 여기서 n>1(내가 배열을 0이 아닌 1부터 입력 받았기 때문)이라고 while문의 조건을 걸어놨는데, 요것이 실수를 불렀다. 위에서 말했다시피 money배열 사이에 위치한 경우를 보기 위해 while문 안에 if (money[n - 1] <= k && k < money[n]) 이런 조건식을 걸었었는데 보니까 n=1일 때를 내가 고려하지 않고 있었다. 그래서 '맞왜틀' 오지게 하고 n=1인 경우를 빼먹었다는 것을 알고 고쳤더니 바로 맞았다 ㅎㅎ;

3. 조건식 안의 구성

k를 money 가치로 나눈 몫을 cnt변수에 넣어주고 나머지를 다시 k에 넣어주는 식으로 구성했다. 그리고 n--

🔨 코드

#include <iostream>
using namespace std;

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

	int n, k;
	cin >> n >> k;
	int money[11] = { 0 };
	while (1) {	//첫 동전의 가치는 1을 입력받아야 함
		cin >> money[1];
		if (money[1] == 1) break;
	}
	for (int i = 2; i <= n; i++) {
		cin >> money[i];
		
		if ((money[i] % money[i - 1]) != 0) i--;	//입력 받은 동전의 가치는 그 전의 배수를 입력받아야 함
	}

	int cnt = 0;
	if (n == 1) { // n이 1인 경우를 생각 못했다..
		cnt += k;
	}
	else {
		while (n>1) {	
			if (money[n] <= k) {	//동전의 가치 중 가장 큰 값이 총 합의 가치보다 크다면
				cnt += (k / money[n]);	// k를 머니의 가치로 나누고 동전 개수 카운트에 저장
				k %= money[n];	// 이제 나머지 값만 필요하므로 나머지 값만 저장
			
			}
			if (money[n - 1] <= k && k < money[n]) {
				cnt += (k / money[n-1]);
				k %= money[n - 1];
				n--;
			}
			else n--;		
		}
	}

	cout << cnt;
	
	return 0;
}