[백준] 1463 1로 만들기 자바 풀이 DP 실버3 쉬운 풀이 완벽 해설

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

 

 

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

1

예제 입력 2 복사

10

예제 출력 2 복사

3

힌트

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

출처

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: cyj101366, jugol
• 어색한 표현을 찾은 사람: dbfldkfdbgml
• 데이터를 추가한 사람: dynamiseus, jooa7878, lcr7324

알고리즘 분류

• 다이나믹 프로그래밍

시간 제한

• Python 3: 1.5 초
• PyPy3: 0.7 초
• Python 2: 1.5 초
• PyPy2: 0.7 초

메모

 

 

 

 

 

핵심 설명

n을 1로 만들지말고

1부터 dp배열을 활용해서 바텀업 방식으로 n을 만들 수 있는 최소연산횟수를 구하자.

 

 

 

 

 

전체코드

import java.io.*;
import java.sql.SQLOutput;
import java.util.*;

public class Main {

    public static long dap = 0;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        // n을 1로 만드는게 아니라,
        // 1부터 바텀업해가면서 n까지 숫자를 만드는데 드는 최소 연산횟수를 dp에 저장해주자.
        long dp[] = new long[n+1];
        dp[0] = 0;
        dp[1] = 0;

        // 1을 만들려면 연산횟수는 0이다. 필요없다
        // 1에서 2를 만들려면 +1하면 된다. 최소연산횟수는 한번
        // 1에서 3을 만들려면 +1+1도 가능하지만, *3하면 된다. 최소연산횟수는 한번
        // 1에서 4를 만들려면 +1+1+1도 가능하지만, *2*2 혹은 *3+1 하면 된다. 최소연산횟수는 두번
        // ...
        // 1에서 9를 만들려면 +1+1+1...도 가능하지만,(3의 dp값)에 *3해서 +1만 해주면 된다! 최소연산횐수 두번
        // 1에서 10을 만들려면 +1+1+1...도 가능하지만, (9의 DP값)에 +1해서, 최소연산횟수는 세번

        //   0 1 2 3 4 5
        // 0 1 2 3 4 5 6
        // 0 0 2 4 6 8 10
        // 0 0 3 6 9 12 15
        for(int i=2; i<=n; i++) {
            // 직전값에서 그냥 덧셈+1해서 한번 카운트 해주는 경우 (이게 최악의 케이스니 일단 dp값 갱신해주자)
            long plusOne = dp[i-1] + 1;
            dp[i] = plusOne;

            // 현재값이 2의 배수인 경우
            if(i%2 == 0){
                // (i/2) 즉 절반의 숫자에 대해서, 곱셈*2해서 i를 만들 수 있으니, 절반숫자dp값에 +1 해주고, plusOne이랑 비교
                long two = dp[i/2] + 1;
                dp[i] = Math.min(dp[i], two);
            }

            // 현재값이 3의 배수인 경우
            if(i%3 == 0){
                // (i/3) 즉 삼등분 숫자에 대해서, 곱셈*3해서 i를 만들 수 있으니, 삼등분숫자dp값에 +1 해주고, 현재dp값이랑 비교
                long three = dp[i/3] + 1;
                dp[i] = Math.min(dp[i], three);
            }

            System.out.println(i + " " + dp[i]);
            // System.out.print(arr[i] + " ");
        }
        dap = dp[n];



        bw.write(String.valueOf(dap) + "\n");
        bw.flush();
        bw.close();
        return;
    }
}