[DP] 백준-거스름돈 C++ 14916번

https://www.acmicpc.net/problem/14916

14916번: 거스름돈

#include <iostream> 
using namespace std;

int dp[100001] = { 0,-1,1,-1,2,1, };
int n;

int main()
{
	cin >> n;
	for (int i = 6; i <= n; i++)
	{
		if (i % 2 == 0)
		{
			dp[i] = dp[i - 2] + 1;
		}
		else
		{
			dp[i] = dp[i - 2] + 1;
		}
		if (i % 5 == 0)
			dp[i] = min(dp[i - 2] + 1, dp[i - 5] + 1);
	}
	cout << dp[n];

	return 0;
}

소감: 처음으로 dp문제를 아무것도 안보고 내손으로 직접 점화식을 찾아서 푼 문제.. 지금까지 어렵게 생각하고 풀 시도조차 못했던 점화식 찾는 문제를..!! 비록 쉬운문제지만 드디어 첫 발을 내딛었다!!!!! 앞으로도 파이팅!!!!