[Java 자바] 백준 알고리즘 2839번 답 : 설탕 배달

 

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

2839번: 설탕 배달

 

---

이 문제,, 다이나믹 프로그래밍으로 분류되어있길래 나는 다이나믹 프로그래밍을 할 줄 몰라서,, 익히고나서 푼 문제!

 

https://youtu.be/5Lu34WIx2Us

(이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍

 

[나동빈님 이코테 강의 (3회 반복) + 이코테 책] 공부해서 이해했음..ㅠ

이거 은근 코드는 엄청 짧은데 생각하는게 어려웠다.

 

그래서 이코테 교재로 공부하다보니 이해가 되더라! 

내가 이해한 부분은 추후 유튜브에 업로드할 예정!.!

 

암튼 그래서 DP 알고리즘을 적용해서 풀었는데 더 효율적으로 푼 방식이 있더라..!

그리디 기법을 쓰면 DP를 이용하지 않고도 풀 수 있는데,, 음,, 근데,, 한번에 떠올리기는 어려운 알고리즘이다.

코드는 매우매우 간단하고 쉽지만, 나라면 이 로직을 절대 생각 못했을 것 같다..ㅎ

---

[DP 알고리즘 적용]

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

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 [] d = new int[N+1];
        d[1] = -1;
        d[2] = -1;
        d[3] = 1;
        if(N>=4)
            d[4] = -1;

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

 

[더 쉬운 알고리즘]

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

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 ans = 0;

        while(N>0){
            if(N % 5 == 0){
                ans++;
                N-=5;
            }
            else{
                ans++;
                N-=3;
            }
        }

        if(N < 0)
            System.out.println(-1);

        else
            System.out.println(ans);
    }
}