백준 2839번 dp

3과 5로 나누어서 떨어지는 수를 최소의 갯수로 나누는 문제이다.
만약 둘의 수로 나누어 떨어지지 않는 다면 -1을 출력한다.

다이나믹 프로그래밍을 처음 접해보았기 때문에 처음 접근은 3과 5로 나누어 떨어지는 수인지 확인한 후 경우의 수를 구해서 최적의 해를 구하려고 했었다.
하지만 이 글에서는 dp 방식으로 접근하려고 한다.

다이나믹 프로그래밍은 현재의 문제들을 이전의 문제의 해결책? 또는 결과값으로 문제를 해결하는 방식이다.
가령, 1부터 10까지 더하는 문제가 있다고 생각해보자.
만약 1부터 9까지 더한 값이 존재한다면, 그 수에 10만 더하면 문제가 해결된다.
이렇게 앞에서 부터 차근차근 문제를 풀어서 저장해 놓는 방식을 dp라고 한다.

import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
   
    if(num<5){
      if(num ==3 ){
        System.out.println(1);
      }
      else
        System.out.println(-1);
      return;
    }
    //0인덱스를 사용하지 않기 때문에 개수 + 1개 배열 생성(인덱스 맞추기)
    int dp[] = new int[num+1];
    //dp는 인덱스만큼에 해당하는 num값이 3과5로 최소 몇개로 나누어지는지 저장
    //초기값으로는 3과 5가 각각 최소 1봉지로 나누어질 수 있다.
    //그 외의 값들은 9999로 채워서 최소값을 갖지 못하도록 한다. 
    Arrays.fill(dp, 9999);
    dp[3] = dp[5] = 1;
    
    //각 인덱스 마다 이전의 값들을 참고하여 최소값을 구한다.
    for(int i=6; i<dp.length; i++){
      dp[i] = Math.min(dp[i-3]+1, dp[i-5]+1);
    }
    //9999이상이라면 나누어 떨어지지 않는다
    if(dp[num]>=9999){
      System.out.println(-1);
    }
    else
      System.out.println(dp[num]);
  }
}