[정올]동전 자판기

문제코드 : 1183

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

#include<stdio.h>

int main()
{
	int w = 0, rw = 0;
	int result = 0;
	int flag = 0;

	int coinN[6] = { 0, };
	int coinRN[6] = { 0, };
	int coin[6] = { 500, 100, 50, 10, 5, 1 };

	int n = 0;
	int i = 0;

	scanf("%d", &w);
	scanf("%d %d %d %d %d %d", &coinN[0], &coinN[1], &coinN[2], &coinN[3], &coinN[4], &coinN[5]);

	for (i = 0; i<6; i++)
	{
		coinRN[i] = w ⁄ coin[i];
		if (coinRN[i] > coinN[i])
			coinRN[i] = coinN[i];
	}

	for (i = 5; i >= 0; i--)
	{
		if (flag == 1)
			coinRN[i] = 0;
		else
		{
			rw += coinRN[i] * coin[i];

			if (w <= rw)
				flag = 1;
		}
	}

	for (i = 0; i < 6; i++)
	{
		if (coinRN[i] != 0 && i != 5)
		{
			if (((coin[i + 1] * coinRN[i + 1]) ⁄ coin[i]) > 0)
				coinRN[i] -= ((coin[i + 1] * coinRN[i + 1]) ⁄ coin[i]);
		}
	}

	rw = 0;

	for (i = 0; i < 6; i++)
	{
		if (coinRN[i] != 0)
		{
			if (i != 5)
			{
				if ((w ⁄ coin[i]) < coinRN[i])
					coinRN[i] = w ⁄ coin[i];
			}
			else
				coinRN[i] = w - rw;

			rw += (coinRN[i]*coin[i]);
		}

		n += coinRN[i];

		if (rw == w)
			break;
	}
	
	printf("%d\n", n);
	for (i = 0; i < 6; i++)
	{
		printf("%d ", coinRN[i]);
	}
	printf("\n");

	return 0;
}