2839 [java] 설탕배달

맨날 까먹어서 매번 다시 풀게 되는..

2023 scpc 1번 문제와 비슷했던 문제

이 문제는 dp로 풀거나, greedy로 풀 수 있다.
그러나 dp로 푸는 풀이를 더 쉽게 떠올릴 수 있는 듯 하다.

dp

import java.util.Scanner;

public class Main {
    static int INF = Integer.MAX_VALUE/4;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int dp[] = new int[N+1];
        dp[0]=0;
        for(int i=1; i<=N; i++){
            dp[i]=INF;
            if(i-3>=0){
                dp[i] = Math.min(dp[i-3]+1, dp[i]);
            }
            if(i-5>=0){
                dp[i] = Math.min(dp[i-5]+1, dp[i]);
            }
        }
        if(dp[N]==INF){
            System.out.println(-1);
        }
        else{
            System.out.println(dp[N]);
        }
        }
}

Greedy

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int total=0;
        while (true){
            if(N%5==0){
                total += N/5;
                System.out.println(total);
                break;
            }
            total++;
            N-=3;
            if(N<0){
                System.out.println(-1);
                break;
            }
        }
    }
}