[백준] 2839 설탕배달 (실버4)

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

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int ans = -1;

        for(int i=0;i<=n/3;i++){
            int five = n - 3*i;
            if(five % 5 ==0){
                ans = i+ five/5;
                break;
            }
        }

        bw.write(String.valueOf(ans));

        bw.flush();
        bw.close();
        br.close();
    }
}

==

import java.util.Scanner;
// 완탐 시간초과!
// 그리디
// 동적계획법
// 개별적인 5kg 를 사용하지 말고 한꺼번에 5kg 를 사용하자 -> 5의 배수를 3으로 만들자.
public class Main {
    static int N, count;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        
        while(true) {
            if( N < 0 ) { // 정확히 떨어지지 않는 경우
                System.out.println(-1);
                break;
            }
            
            if( N % 5 == 0 ) {
                System.out.println(count + N / 5); // 5 모두 사용
                break;
            }
            
            // 3 사용
            N -= 3;
            count++;
            
        }
    }
}

• 추가)
  dp 방식

static int[] bag;
static int dp(int n){
    if(n<=5){
        if(n==3 || n==5) return 1;
        else return -1;
    }
    bag = new int[n+1];
    Arrays.fill(bag,5000); //비교를 위해 제일 큰 값으로 초기화
    
    bag[3] = 1;
    bag[5] = 1;
    
    for(int i=6;i<=n;i++){
        bag[i] = Math.min(bag[i-3] + 1, bag[i-5] + 1);
    }
    return bag[n]>=5000 ? -1:bag[n];
}