ACM 674, Coin Change

마지막으로 ACM 문제를 풀어본 지가 2006년이니까 정말 많은 세월이 지났네. 이제 다시 풀려니까 다시 시작하는 것하고 똑같군... 괜히 공부는 꾸준히 해야한다고 하는 게 아니군. 어쨌건 동전 문제를 푼 기념으로 ACM 문제를 찾아보니 뭐 완전 똑같네.

코드를 살짝 고쳐서 올려서 Accepted. 처음에는 멍청하게 값을 입력받을 때마다 계산해서 시간 초과... 생각해보니 결과는 미리 정해진 거 잖아. 상위권에 엄청난 속도로 푼 기록들이 있는데 미리 계산된 테이블을 사용한 듯 싶더라구. 나는 이걸 템플릿으로 만들어보려고 하는데 흠... 고민 중. 그것도 그렇고 다른 사람들이 푼 걸 봤는데 내 것보다 메모리 사용이 1/5 밖에 안 쓰더라구. 헐.

674.pdf

// ACM 674

#include < stdio.h >
#include < iostream >

int main(int argc, char* argv[])
{
	const int maxCoinCount = 5;
	const int maxMoney = 7489;

	int coins[ maxCoinCount ] = { 1, 5, 10, 25, 50 };
	int coinCount = 5;

	int results[ maxCoinCount + 1 ][ maxMoney + 1 ] = {};
	for(int coinIndex = 0; coinIndex < coinCount; ++coinIndex)
	{
		const int coin = coins[ coinIndex ];
		int* const result = results[ coinIndex + 1 ];
		int* const prevResult = results[ coinIndex ];

		// 자기 자신으로 나누는 경우는 항상 1이다.
		result[ 0 ] = 1;

		// 이전 값을 가져온다
		for(int money = 1; money < coin; ++money)
		{
			result[ money ] = prevResult[ money ];
		}

		for(int money = coin; money <= maxMoney; ++money)
		{
			int& count = result[ money ];
			int countExceptCoin = prevResult[ money ];
			count += countExceptCoin;

			int countWithCoin = result[ money - coin ];
			count += countWithCoin;
		}
	}

	int totalMoney;
	while(scanf( "%d", &totalMoney ) == 1)
	{
		std::cout << results[ coinCount ][ totalMoney ] << std::endl;
	}

	return 0;
}