[Java] 백준 2839번 설탕 배달

2839번: 설탕 배달

---

풀이

DP를 사용하여 해결했습니다.

 

N까지의 최소의 수를 구해야하기때문에 memo 배열을 Integer.MAX_VALUE로 초기화하여 만약 아무런 봉지를 선택안하거나 둘 중 하나만 선택하는 경우에서 잘못된 값이 들어가지 않게 했습니다.

---

코드

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

public class Main {
	public static int N;
	public static int[] memo = new int[5001];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		Arrays.fill(memo, Integer.MAX_VALUE);
		
		memo[3] = 1;
		memo[5] = 1;
		for (int i = 6; i <= N; ++i) {
			int min = Math.min(memo[i - 3], memo[i - 5]);
			
			if (min != Integer.MAX_VALUE) {
				memo[i] = min + 1;				
			}
		}
		
		System.out.println((memo[N] == Integer.MAX_VALUE) ? -1 : memo[N]);
	}
}

---

pyo7410/Algorithm