[백준] 2839 설탕 배달 - DP + 그리디 JAVA

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

2839번: 설탕 배달

코드설명

DP 혹은 그리디 문제입니다.

 

DP 방식으로도 풀 수 있고,

그리디스럽게도 풀 수 있습니다.

 

DP와 그리디의 방법 2가지로 모두 풀어보았습니다.

 

코드

DP Bottom Up

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

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	if( N < 5) {
    		if(N == 3) System.out.println("1");
    		else System.out.println("-1");
    		return ;
    	}
    	
    	dp = new int[N+1];
    	
    	dp[3] = 1;
    	dp[5] = 1;
    	
    	for(int i = 6; i<=N;i++) {
    		if(i % 5 == 0) {
    			dp[i] = dp[i-5] + 1;
    		}
    		else if(i % 3 == 0) {
    			dp[i] = dp[i-3] + 1;
    		}
    		else if(dp[i-3] > 0 && dp[i-5] > 0) {
    			dp[i] = Math.min(dp[i-3] + 1,  dp[i-5] + 1);	
    		}
    		
    	}
    	
    	if(dp[N] == 0) {
    		System.out.println("-1");
    		return ;
    	}
    	
    	System.out.println(dp[N]);
    }

   
}

 

 

구현을 활용 ( 그리디 )

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

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	while( N > 0) {
    		if( N % 5 == 0) {
    			answer += N / 5;
    			System.out.println(answer);
    			return ;
    		}
    		if( N < 3) {
    			System.out.println("-1");
    			return ;
    		}
    		N -= 3;
    		answer += 1;
    	}
    	System.out.println(answer);
    }

   
}