99클럽 코테 스터디 14일차 TIL: DP

문제

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

풀이

DP로 쉽게 풀 수 있는 문제이다.
Bottom-Up 방식으로 풀이하였고, 메모이제이션 하기 위한 1차원 Int 배열을 선언하고, 값을 큰 값(INF)으로 초기화해주었다.

먼저 2원과 5원만 존재하기 때문에 다음과 같이 기본값을 셋팅했다.

dp[2] = 1
dp[4] = 2
dp[5] = 1

이제 6부터 N의 최대값인 10만까지 반복문을 돌려야겠다고 생각했다.
6원을 만드는 경우의 수는 4원에서 2원을 더하는 것과 1원에서 5원을 더하는 두가지 방법잉있다.
하지만 1원을 만드는 방법은 없어서 4원에서 2원을 더하는 것이 최소 횟수이다.

초기값: $f(2) = 1, f(4) = 2, f(5) = 1$

다음과 같은 점화식을 유추할 수 있다.
$if\ (n \ge 6),\ f(n) = min(f(n - 2), f(n - 5)) + 1$

이후, f(n)의 값을 구하면 되는 문제이다.
f(n)이 INF 값보다 크거나 같다면 -1을 출력해주자.

소스코드

후기

DP를 되게 어려워하는데 이 문제는 쉽게 풀었다.
기초적인 DP 문제였다.