[자바] 백준 2839 설탕배달

상근이는 참 열심히 사는군요. 

 

설탕공장에서 사탕가게에 설탕도 배달해주고

 

N은 최대 5000이니까..5000kg까지...호..상근이 운동 좀 치겠는데.

 

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

2839번: 설탕 배달

 

<나의 풀이>

 

이상하게 잘 안풀리는 문제였습니다. 

 

그건 아마도 제가 DP가 익숙하지 않은 탓 이겠죠. 

 

분명 민경하 교수님이 DP를 만나면 고맙다고 하라고 했는데....교수님의 말씀을 그대로 믿은 제 잘 못일까요. 

 

문제는 간단합니다. 

 

3<= N <=5000을 3과 5를 최소한으로 빼며 0으로 만들기

 

사실 보자마자 점화식이 떠올르긴 했습니다. 

 

Divde(n) = Math.min(Divde(n-5)+1 , Divide(n-3)+1)

이를 구현하면됩니다. 

 

근데 나눠지지 않는 값을 처리하는데 살짝 어려움이 있었습니다. 0으로 두자니 최솟값 갱신이 안되고, INTEGER_MAX_VALUE로 두자니 1이 더해지면서 INTEGER_MIN_VALUE로 되어서 또 최솟값 갱신에 문제가 생겼습니다. 

 

그래서 초기 값을 5000/3 해서 ..이쁘게 2000으로 두고 풀었습니다.

 

DP는 결국 Memoziation인 것 일까요.

 

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

public class Main {
    static int[] vist;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        vist = new int[5001];
        vist[3] = 1;
        vist[5] =1;
        vist[n]=dp(n);
        if(vist[n] >=2000){
            System.out.println(-1);
        }else{
            System.out.println(vist[n]);
        }
        //System.out.println(Arrays.toString(vist));
    }
    public static int dp(int n) {
        if(n<3){
            return 2000;
        }
        if(n==3) return 1;
        if(n<5) return 2000;
        if(n==5) return 1;
        if(vist[n]!=0) return vist[n];
        vist[n] = Math.min(dp(n-5)+1,dp(n-3)+1);
        return vist[n];
    }
}