dp기본 문제

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

2839번: 설탕 배달

package dp;

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

public class bj_설탕배달_복습_2839 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int arr[] = new int[N + 1];
		arr[3] = 1;
		if (N >= 5) {
			arr[5] = 1;
		}
		for (int i = 6; i <= N; i++) {
			if (i % 5 == 0) {
				arr[i] = arr[i - 5] + 1;
			} else if (i % 3 == 0) {
				arr[i] = arr[i - 3] + 1;
			} else if (arr[i - 5] != 0 && arr[i - 3] != 0) {
				arr[i] = Math.min(arr[i - 5], arr[i - 3]) + 1;
			}
		}
		if (arr[N] == 0) {
			System.out.println("-1");
			return;
		}
		System.out.println(arr[N]);
	}
}

3과 5는 일단 답인 1로 초기화를 해주고 4는 어짜피 답이 -1이기 때문에 굳이 초기화를 해줄 필요가 없다. 

처음으로 5로 나누어줬을 때 나머지가 0이라면 전에 -5인 값에 다가 1만 더해주면 최소값이 될수도 있기 때문에 일단 그렇게 값을 저장해준다. 

3도 마찬가지로 3으로 나눴을 때 나머지가 0이라면 -3인 값에다가 1만 더해주면 최소값이 될 수 있기 때문에 일단 저장을 해둔다.

5부터 하는 이유는 더 큰 숫자로 나눴을 때 답에 더 가까워질 수 있기 때문이다.

그리고 18같은 숫자는 6이 답이 아닌 5/5/5/3인 4개가 답이기 때문에 마지막 if문인 -3과 -5에서의 최소값을 비교해주고 거기에 1만 더해주면 답이 되기 때문에 그걸 더해준다.