17212달나라 토끼를 위한 구매대금 지불 도우미

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

DP배열 만들고 인덱스가 금액. 값이 동전개수

구하려는 금액의 인덱스 = 금액인덱스 -1, -2, -5, -7 의 인덱스들 중에서 동전개수 가장 작은거 + 1

DP문제중에 계단 문제가 잇는데 비슷하다
구하려는 계단의 인덱스로 올 수 있는 방법은 1, 2, 5, 7 전에 인덱스들이므로 그 중에 가장 작은 걸음횟수 + 1 을 하면 구하려는 계단까지 걸음횟수를 구할 수 있다.

이번에도 규칙을 찾지못해서 검색해보고 풀었다...

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args)throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int money = Integer.parseInt(br.readLine());

        int[] coin = {1, 2, 5, 7};

        int[] dp = new int[100001];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 2;
        dp[5] = 1;
        dp[6] = 2;
        dp[7] = 1;

        for (int i = 8; i <= money; i++) {
            dp[i] = Math.min( dp[i-1], Math.min(dp[i-2], Math.min(dp[i-5], dp[i-7])))+1;
        }

        System.out.println(dp[money]);
    }
}