2294번: 동전 2

Memo

• "동전 1"과의 차이점은 갯수의 최소값을 구하는 것입니다.
• 갯수의 최대값은 1로 10,000을 만드는 갯수인 10,000 입니다.
• 입력을 오름차순으로 받아야 로직이 정상 동작합니다. (sorting 적용)

나눗셈 연산은 비싸다

• 처음 코드 (4ms)

void solve()
{
	size_t ind;

	for (size_t i = 0 ; i < n ; i++)
	{
		ind = coins[i];
		for (size_t j = ind; j <= k ; j++)
		{
			if (dp[j - ind] != _MAX)
				dp[j] = std::min(dp[j], dp[j - ind] + 1);
			else if (!(j % ind))
				dp[j] = j / ind;
		}
	}
}

• 나머지 연산을 위로 올린 코드 (8ms)

void solve()
{
	size_t ind;

	for (size_t i = 0 ; i < n ; i++)
	{
		ind = coins[i];
		for (size_t j = ind; j <= k ; j++)
		{
			if (!(j % ind))
				dp[j] = j / ind;
			else if (dp[j - ind] != _MAX)
				dp[j] = std::min(dp[j], dp[j - ind] + 1);
		}
	}
}

• 나머지 연산을 없앤 나중 코드 (0ms)

void solve()
{
	size_t ind;

	for (size_t i = 0 ; i < n ; i++)
	{
		ind = coins[i];
		dp[ind] = 1;
		for (size_t j = ind; j <= k ; j++)
			if (dp[j - ind] + 1 < dp[j])
				dp[j] = dp[j - ind] + 1;
	}
}