백준 1463 1로 만들기(Java)

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

1463번: 1로 만들기

---

 

해석 및 팁

 

---

 

이 문제는 단순히 3으로 나누어 떨어지면 3으로 나누고 2로 떨어지면 2로 나누면 안 됩니다.  10인경우에 10->5->4->2->1 인경우에는 4번이지만 10->9->3->1 인경우네는 3번 만에 1로 만들 수 있습니다. 따라서 2와 3으로 나누어 떨어지지 않는 경우에는 1을 빼고 나누어 떨어지는 경우에는 나누는 경우와 1을 빼는 경우를 비교하여 최솟값을 출력하면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

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

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

    arr[1] = 0;
  
    for(int i = 2; i <= n; i++) {
      arr[i] = arr[i - 1] + 1;
      if(i % 2 == 0) arr[i] = Math.min(arr[i], arr[i / 2] + 1);
      if(i % 3 == 0) arr[i] = Math.min(arr[i], arr[i / 3] + 1);
    }

    System.out.println(arr[n]);
  }
}