백준 2839번 설탕 배달

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Sugar_Deliver {
    static int[] dp;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int[5001];
        dp[0] = Integer.MAX_VALUE;
        dp[1]= Integer.MAX_VALUE;
        dp[2] = Integer.MAX_VALUE;
        dp[3] = 1;
        dp[5] = 1;
        dp[4] = Integer.MAX_VALUE;
        dp[7] = Integer.MAX_VALUE;
        dp[6] = 2;
        cal(N);
        if(N==4||N==7){
            System.out.println(-1);
        }
        else {
            System.out.println(dp[N]);
        }

    }
    public static int cal(int n){
        if(dp[n]==0){
            dp[n] = Math.min(cal(n-3),cal(n-5))+1;
        }
        return dp[n];
    }
}

풀이방법

📢 이풀이의 핵심은 dp[n]에 3과 5를 최소로 사용하여 n을 만들수 있는 값을 넣어주는 것이다.
이때, dp[n]값이 dp[n-3], dp[n-5] 중에 하나에서 1이 증가한 값이다.
이 문제에서는 가장 적은 개수로 만들어야 하기때문에 Math.min을 사용하여 설계해준다.
이때, 4와 7은 어떠한 방법으로도 만들 수 없기때문에 -1처리를 해준다.

후기

dp[n] = Math.min(cal(n-3),cal(n-5))+1;
이 핵심코드를 파악하는것이 문제 푸는 핵심이다.