[그리디, DP] 백준 2839. 설탕 배달

import java.util.*;
import java.io.*;

public class BackJoonMemo {
    static int[] cards;
    static boolean[] visited;
    static int n, m, result, check;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 배달할 설탕의 무게 (kg)
        n = Integer.parseInt(st.nextToken());
        int five = 0, three = 0;

        int[] sugarW = new int[5001];

        for(int i = 0; i<n+1; i++){
            sugarW[i] = -1;
        }

        sugarW[0] = 0;
        sugarW[3] = 1;
        sugarW[5] = 1;
        
        for(int i = 6; i<n+1; i++){
            if(sugarW[i-5] != -1){ // 5의 배수일 때
                sugarW[i] = sugarW[i-5] + 1;
            }
            if(sugarW[i-3] != -1){ // 3의 배수일 떄
                if(sugarW[i] != -1){
                    sugarW[i] = Math.min(sugarW[i-3] + 1, sugarW[i]);
                    continue;
                }
                sugarW[i] = sugarW[i-3] + 1;
            }
        }

        //for(int i = 0; i<n+1; i++){
        //    System.out.println(i + ": " + sugarW[i]);
        //}

        System.out.println(sugarW[n]);


    }



}
/**
 * if(n % 5 == 0){ // 5의 배수일 경우
 *                 five += n / 5;
 *                 n %= 5;
 *             }
 *             else if(n % 3 == 0){ // 5의 배수가 아니고 3의 배수 일 경우
 *                 three += n / 3;
 *                 n %= 3;
 *             }
 *             else if(n >= 5){ // 5, 3 배수 어떤 것도 아닌 경우 (5kg 봉지로 가져가는게 제일 적게 들고가는 방법)
 *                 five += n / 5;
 *                 n %= 5;
 *             }
 *             else if(n < 5 && n >= 3){ // 3kg 봉지를 들고갈 수 있는 경우의 수
 *                 three += n / 4;
 *                 n %= 4;
 *             }
 *             else{
 *                 n -= 1;
 *                 validate = true;
 *             }
 */

모범 답안..(그리디)

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

public class Main {
public static void main(String[] args) throws IOException {

   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   int N = Integer.parseInt(br.readLine());
   int X = 0;
   
   while(true) {
	   if(N%5 == 0) {
		   System.out.println(N/5 + X);
		   break;
	   } else if (N<0) {
		   System.out.println(-1);
		   break;
	   }
	   N -= 3;
	   X++;
   }
}

}