BOJ Q.2839 설탕공장 문제입니다.
   
동적프로그래밍 방식으로도 풀이가 가능하기에

이번에는 동적프로그래밍 방식으로 풀이 해보겠습니다.

N킬로그램까지 모두 MAX 값으로 초기화를 해줍니다.

i무게까지의 봉지 개수를 제일 적게 해야하므로

i-3까지의 봉지 개수 와 i-5까지의 봉지 개수 중 

더 적은 봉지 개수에 3kg 짜리 또는 5kg짜리 봉지 하나를

추가해주면 됩니다.

d[i] = MIN (d[i-3],d[i-5]  +1

i-3 , i-5 모두 MAX 값이라면 불가능한 조합입니다.

d[i]에 

MAX로 남아있는 경우는 불가능한 조합이고

그 외는 가능한 제일 적은 봉지 개수가 저장됩니다.

package problem.dynamic;

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

public class Main_2839 {

    static int N;
    static int d[];
    static final int MAX = 5001;

    public static void main(String[] args) throws IOException {
        input();
        int result = solve();
        if(result==MAX){
            result= -1;
        }
        System.out.println(result);
    }

    public static int solve(){
        for(int i=0; i<=N; i++){
            d[i] = MAX;
        }
        d[3] = 1;
        d[5] = 1;
        for(int i=5; i<=N; i++){
            if(d[i-3]== MAX && d[i-5]== MAX) {
                continue;
            }
            d[i] = Math.min(d[i-3],d[i-5])+1;
        }
        return d[N];
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        d = new int[MAX];
        br.close();
    }

}