정올 1183 동전 자판기(下) 문제풀이

정올 문제풀이

1183 : 동전 자판기(下)

 

 

 

문제

철수는 동전 자판기를 자주 이용한다. 
그래서 그는 항상 상당히 많은 개수의 동전들을 주머니에 가지고 다니는데, 동전들이 주머니에서 짤랑거리는 것을 듣기 싫어한다.
그래서 철수는 동전자판기에서 무언가 살 때는 되도록 많은 개수의 동전을 사용한다.
철수의 주위에 있는 자판기들은 아주 구형인 모델이어서 지폐를 사용할 수 없고, 또, 정확한 액수만을 넣어야 한다.
이 문제는 철수가 가지고 있는 동전 중 최대 개수의 동전을 이용하여 자판기의 물건을 구입하는 방법을 출력하는 프로그램을 작성하는 것이다.

 

 

입력형식

첫줄에는 자판기에서 구입하려는 물건의 값 W가 주어진다.
둘째줄에는 6개의 정수가 주어진다.
각각의 정수는 철수가 가지고 있는 500원짜리, 100원짜리, 50원짜리, 10원짜리, 5원짜리, 1원짜리 동전들의 개수를 순서대로 나타낸다.
각각의 동전 개수는 1 이상 10 이하이다. 정수들 사이에는 빈칸이 하나 있다.

 

 

출력형식

첫 줄에는 물건의 구입에 사용될 수 있는 최대 개수의 동전수를 출력한다.

둘째줄에는 최대 개수를 구성하는 동전들에 대해 500원짜리부터 시작하여 각각의 개수를 순서대로 출력한다. 

즉, 6개의 정수가 출력되어야 하며 사용하지 않는 액수의 동전이 있으면 그 액수에 대해서는0을 출력한다. 

 

※ 어떠한 동전들의 조합으로도 정확한 물건값이 될 수 없는 경우는 입력으로 주어지지 않는다.

 

 

입력 예	출력 예
13 4 5 2 6 3 4	5 0 0 0 0 2 3

 

 

제출코드

C++

#include <stdio.h>

int w;
int price[6] = { 500, 100, 50, 10, 5, 1 };
int countArr[6];

int main()
{
	int i, j;
	int sum = 0;

	scanf("%d", &w);

	for (i = 0; i < 6; i++)
	{
		scanf("%d", countArr + i);
		sum += price[i] * countArr[i];
	}

	for (i = 0; i < 6; i++)
	{
		int cnt = countArr[i];
		for (j = 0; j < countArr[i]; j++)
		{
			if (sum == w)
			{
				countArr[i] = cnt;
				goto Point;
			}
			
			int tmp = sum - price[i];
			if (tmp < w)
				break;

			sum = tmp;
			--cnt;
		}
		countArr[i] = cnt;
	}

Point:
	int count = 0;
	for (i = 0; i < 6; i++)
		count += countArr[i];
	printf("%d\n", count);

	for (i = 0; i < 6; i++)
		printf("%d ", countArr[i]);

	return 0;
}