백준 12852 1로 만들기 2(Java)

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

12852번: 1로 만들기 2

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    int n = sc.nextInt();
    
    int[] arr = new int[n + 1];
    int[] num = new int[n + 1];

    arr[1] = 0;
  
    for(int i = 2; i <= n; i++) {
      arr[i] = arr[i - 1] + 1;
      num[i] = i - 1;
      if(i % 2 == 0 && arr[i / 2] + 1 < arr[i]) {
        arr[i] = arr[i / 2] + 1;
        num[i] = i / 2;
      }
      
      if(i % 3 == 0 && arr[i / 3] + 1 < arr[i]) {
        arr[i] = arr[i / 3] + 1;
        num[i] = i / 3;
      }
    }
    
    sb.append(arr[n]+"\n");

    while(n > 0) {
      sb.append(n+" ");
      n = num[n];
    }
    System.out.println(sb);
  }
}