[백준/그리디, DP] 2839: 설탕배달 - 자바

문제

---

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

2839번: 설탕 배달

 

풀이

크게 두가지 방법으로 풀 수 있다. 

하나는 반복문과 재귀를 사용하여 나머지 하나는 DP를 사용하여 풀었다.

오히려 DP를 사용하는 것이 반복문보다 많은 시간이 걸렸다.

 

반복문 이용

public class BOJ_2839_Sol1 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int cnt = 0;
		while (N > 0) {
			if (N % 5 == 0) {
				cnt += N / 5;
				N = 0;
				break;
			}
			cnt++;
			N -= 3;
		}
		if (N < 0)
			System.out.println("-1");
		else
			System.out.println(cnt);
	}
}

 

재귀 이용

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

public class BOJ_2839_Sol2 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		check(N,0);
	}
	static void check (int N,int idx) {
		if ( N%5 ==0) {
			System.out.println(idx+N/5);
			return;
		}
		if (N<0) {
			System.out.println(-1);
			return;
		}
		check (N-3,idx+1);
	}
}

 

DP 이용

public class BOJ_2839_Sol3 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[N+5];
		int maxVal = 5000/3+1;
        
		Arrays.fill(dp,maxVal);
		dp[3] = dp[5] = 1;
        
		for(int i = 6; i <= N+1; i++) dp[i] = Math.min(dp[i-3], dp[i-5]) + 1;
        
		bw.write(String.valueOf(dp[N] >= maxVal ? -1 : dp[N]));
		bw.flush();
		bw.close();
	}
}