백준 1463 1로 만들기 (Java)

URL

www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제

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

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

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

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

입력

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

출력

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

생각

• 정수 X를 1로 만드는데 필요한 최소 연산 횟수를 배열에 저장한다. (d[x])

• 정수 X가 3으로 나누어 떨어질 때, 3으로 나누는 경우 => d[X/3] + 1

• 정수 X가 2으로 나누어 떨어질 때, 2으로 나누는 경우 => d[X/2] + 1

• 정수 X에서 1을 빼는 경우 => d[X-1] + 1

• d[x]에는 세 경우의 결과 중, 최소값을 담는다.

• 다이나믹 프로그래밍의 해결 방법 중, Buttom-up 방법으로 문제를 풀었다. (https://bellossimo.tistory.com/63)

다이나믹 프로그래밍 (Dynamic Programming)

성공 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] d = new int[1000001];
        int input = scanner.nextInt();

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

            if(i%2 == 0 && d[i] > d[i/2] + 1) {
                d[i] = d[i/2] + 1;
            }

            if(i%3 == 0 && d[i] > d[i/3] + 1) {
                d[i] = d[i/3] + 1;
            }
        }

        System.out.println(d[input]);
    }
}