[Java] 백준 2839번 : 설탕 배달

문제

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

 

접근 방법

1. 3키로와 5키로 봉지가 있을때 최대한 적은 봉지를 쓰는 문제입니다.

2. N이 주어졌을때 5키로 나누어지거나 , 3키로로 나누어지거나, dp[i-5] != 0, dp[i-3] != 0 이라면 3이나 5로 나누어지므로 dp를 만들어 풀어줬습니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N;
    private static int[]dp;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        dp = new int[N+1];
    }

    //실행
    public static void process() {
        if(N >= 3) dp[3] = 1;

        if(N >= 5) dp[5] = 1;

        for(int  i = 6 ; i <= N ; i++){
            if(i % 5 == 0){
                dp[i] = dp[i-5]+1;
            }else if(i % 3 == 0){
                dp[i] = dp[i-3]+1;
            }else{
                if(dp[i-3] != 0 && dp[i-5] != 0){
                    dp[i] = Math.min(dp[i-3],dp[i-5]) + 1;
                }
            }
        }
        System.out.println(dp[N] == 0 ? -1 : dp[N]);
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}