백준 2839 (설탕 배달) - java

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

2839번: 설탕 배달

3으로 나눠지는 경우 / 5로 나눠지는 경우 / dp[i-3]의 값이 1 이상인 경우 / dp[i-5]의 값이 1 이상인 경우 중에 최솟값을 구하면 된다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int[] dp = new int[5001];
    static int n= 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp[3] = 1;
        dp[5] = 1;
        for(int i=4;i<=n;i++)
        {
            int n1=5001,n2=5001,n3=5001,n4=5001;
            if(i%3==0) // 3으로 나눠지는 경우
            {
                n1 = i/3;
            }
            if(i%5==0) // 5로 나눠지는 경우
            {
                n2 = i/5;
            }
            if(i-3>=3&&dp[i-3]!=0) // dp[i-3]이 1 이상인 경우
            {
                n3 = dp[i-3]+1;
            }
            if(i-5>=5&&dp[i-5]!=0) // dp[i-5]이 1 이상인 경우
            {
                n3 = dp[i-5]+1;
            }
            int re = Math.min(Math.min(n1,n2),Math.min(n3,n4)); // 경우중 최솟값
            if(re!=5001)
            {
                dp[i]=re;
            }
        }
        if(dp[n]==0)
        {
            System.out.println(-1);
        }
        else{
            System.out.println(dp[n]);
        }

        br.close();
    }
}