[백준] 1463번 1로 만들기

출처

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

1463번: 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제

내 코드

1. 입력한 숫자를 1로 만드는 최소의 연산 숫자이므로 1의 연산 최솟값은 0이다.

2. for문은 2부터 시작해서 N까지 돌게 한다.

3. arr[i]는 먼저 이전 칸 값의 +1을 하는데 이는 3번연산을 수행한 것이다.

4. 첫 번째 if 내에서는 3번 연산을 한 값과 나누기 2 한 값에 +1을 했을 때의 값을 비교해 최솟값을 넣는다.

5. 3번 연산만 거쳤으면 3번 연산의 값과 나누기 3한 값에 +1 한 값이 비교되고, 2번 연산까지 거치게 되었으면 2번 연산의 값과 나누기 3한 값에 +1 한 값이 비교된다.

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        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                            //3번 연산

            if (i % 2 == 0)
                arr[i] = Math.min(arr[i], arr[i / 2] + 1);	//2번 연산

            if (i % 3 == 0)
                arr[i] = Math.min(arr[i], arr[i / 3] + 1);	//1번 연산
        }
        System.out.print(arr[N]);
    }
}