다시 해본 동전 문제

책장 한 켠에 오랫동안 꽂혀있는 출력물이 있어. 무엇인가 하면은 어느 회사에 입사하기 위해서 꼭 풀어야하는 문제 목록이야. 간만에 봤는데 동적 프로그래밍으로 해결해야 하는 문제 같더군. 그건 풀면 올려보기로 하고. 어쨌거나 회사 생활 동안 공부를 게을리했더니 이런 문제가 낯설고 힘들더군...

암튼 다시 공부했는데 개념은 쉬워보이지만 이해하는데 꽤 시간이 걸려버렸네. 이 바닥에서 기본적인 동전 문제를 다시 풀어보기로 했는데 우와 어렵다... 예전에는 어떻게 풀었을까. 이해하는데 3일은 걸린 것 같아. 코딩하는데도 3일? 흑... 부끄럽네. 그래도 스스로 해결했다는데 만족하고. 일단 예전 코드와 비교하니 라인 수는 줄어든 것 같아. 그나마 자기 만족꺼리는 생겼어  흐.... 알고리즘은 정말 모든 곳에 필요한데 말야. 지금 취미로 만드는 미니 게임에도 알고리즘이 꽤 필요하거든. 벼락치기로는 안되니 조금씩 해보기로 다짐하는데 어떨까.

// #include "stdafx.h"
#include < iostream >

int main(int argc, char* argv[])
{
	const int maxCoinCount = 20;
	const int maxMoney = 10000;
	int caseCount;
	std::cin >> caseCount;

	while(--caseCount >= 0)
	{
		int coinCount;
		std::cin >> coinCount;

		int coins[ maxCoinCount ] = {};
		for(size_t i = 0; i < coinCount; ++i)
		{
			int coin;
			std::cin >> coin;
			coins[ i ] = coin;
		}

		int totalMoney;
		std::cin >> totalMoney;

		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 <= totalMoney; ++money)
			{
				int& nominal = result[ money ];
				int nominalExceptCoin = prevResult[ money ];
				nominal += nominalExceptCoin;

				int norminalWithCoin = result[ money - coin ];
				nominal += norminalWithCoin;
			}
		}

		std::cout << results[ coinCount ][ totalMoney ];
	}

	return 0;
}