1로 만들기.java

import java.util.*;

public class Main{
  public static int[] d = new int[30001];

  public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    for (int i = 2;i<=n;i++){
      d[i] = d[i - 1] + 1;

      if(i%2 ==0){
        d[i] = Math.min(d[i],d[i/2] + 1);
      }
      else if(i%3 == 0){
        d[i] = Math.min(d[i],d[i/3] + 1);
      }
      else if(i%5 == 0){
        d[i] = Math.min(d[i],d[i/5] + 1);
      }
    }
    System.out.println(d[n]);
  }
}