1로 만들기(1463)

메모이제이션으로 N을 1로 바꾸기 위해 주어진 연산을 몇 번 사용하는지 계산하는 문제

문제

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

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

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

3. 1을 뺀다.

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

시간제한이 0.15초

입력

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

출력

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

예제 입력

2

예제 출력

1

예제 입력2

10

예제 출력2

3

힌트

10의 경우에 10->9->3->1로 3번 만에 만들 수 있다.

풀이

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[N+1];
        //식은 기본적으로 2개가 있어야 하나가 있게되니까 0과 1은 0으로 초기화
        dp[0] = 0;
        dp[1] = 0;
        for(int i=2; i<=N; i++){
            //계산식을 보면 N개의 항목이 있을때는 수식은 N-1개가 되기 때문에 dp에 수식의 갯수를 저장
            dp[i] = dp[i-1]+1;
            if(i%2==0)
                dp[i] = Math.min(dp[i], dp[i/2]+1);
            if(i%3==0)
                dp[i] = Math.min(dp[i], dp[i/3]+1);
        }

        System.out.println(dp[N]);

    }

}

백준