[백준 2839번] 설탕배달 - JAVA

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

2839번: 설탕 배달

풀이

사용한 알고리즘 : 다이나믹 프로그래밍(DP)

 

풀이전략

1~5000까지의 입력이 주어진다고 했으므로 바텀업 방식으로 1kg부터 5000kg까지의 결과값을 미리 구한다.

i kg일 때 최소의 설탕 봉지 수는, i-3 kg에서와 i-5 kg에서의 최소 봉지수에 1을 더한 값 중 더 작은 값이다.

단, i-3 kg에서와 i-5 kg에서 3kg와 5kg 봉지를 갖고 모두 담을 수 있는 경우에서 적용된다.

1) i-3 kg에서 최소 봉지수를 가지나, i-5 kg에서 최소 봉지수를 가지지 못할 경우

   d[i]=d[i-3]+1

2) i-5 kg에서 최소 봉지수를 가지나, i-3 kg에서 최소 봉지수를 가지지 못할 경우

   d[i]=d[i-5]+1

3) i-3 kg와 i-5 kg에서 둘 다 최소 봉지수를 가지지 못할 경우

   d[i]=-1

4) i-3 kg와 i-5 kg에서 둘다 최소 봉지수를 가지는 경우

   d[i]=Math.min(d[i-3]+1,d[i-5]+1)

 

제출코드

import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N=scanner.nextInt();

        int d[]=new int[5001];
        d[1]=-1;
        d[2]=-1;
        d[3]=1;
        d[4]=-1;
        d[5]=1;

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