[백준/C & C++] 11047 동전 0

 

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

11047번: 동전 0

코드 (C)

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int n, money, count=0;
	scanf("%d %d", &n, &money);
	int* arr = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);


	for (int i = n-1; i >= 0; i--)
	{
		if (money == 0) break;
		count += money / arr[i];
		money %= arr[i];
	}

	printf("%d", count);
	free(arr);
	return 0;
}

코드 (C++)

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

int main()
{
	int n, money, count = 0;
	cin >> n >> money;

	int* arr = new int[n];
	for (int i = 0; i < n; i++) cin >> arr[i];
	
	for (int i = n - 1; i >= 0; i--)
	{
		if (money == 0)break;
		count += money / arr[i];
		money %= arr[i];
	}

	cout << count;
	delete[]arr;
	return 0;
}

코드설명

동적배열을 선언해서 동전의 가치를 계속 입력받는다. 

동전의 가치는 오름차순으로 입력되었으므로 역순으로 반복문을 돈다. 

만약 money가 0이 되면(count를 다 함) 반복문을 나간다. 

그렇지 않으면 count에 돈/동전의 가치 더한다. (동전의 개수를 더해나감.) 그 후 돈을 동전의 가치로 나눈 나머지가 돈이 되게 한다. 

느낀 점

동전 개수의 최솟값을 구해야 하므로 역순으로 반복문을 돌게 했다. 풀이방식을 생각한 후 금방 풀었다.