백준) 1463 : 1로 만들기

⏰ 문제

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.15 초 (https://www.acmicpc.net/problem/1463#)	128 MB	288374	97925	62437	32.854%

 

정수 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번 만에 만들 수 있다.

 

💡풀이

1. 테이블 정의하기- D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값

 

2. 점화식 찾기예를 들어서  D[12]라는 것을 어떻게 구해야 할지 생각해본다. 만약 D[1]부터 D[11]을 다 알고 있다는 가정하에서, D[12]는 3으로 나누거나, 2로 나누거나, 1을 빼서 구할 수 있다. 즉, D[12] = min(D[4] + 1, D[6]+1, D[11]+1)로 구할 수 있다. 

 

이 식을 일반화하면 D[k] = min(D[k/2]+1, D[k/3]+1, D[k-1]+1)가 된다. 

 

3. 초기값 정의하기D[1] = 0으로 점화식의 초기값을 설정해주면 문제를 풀 수 있다. 점화식에서는 초기값을 어디까지 정의해줄 것인지가 가장 중요!

 

⌨️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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];

        dp[1] = 0;

        for(int i=2; i <= N; i++){
            dp[i] = dp[i-1] + 1;

            if(i % 2 == 0) {
                dp[i] = Integer.min(dp[i], dp[i/2]+1);
            }
           if(i%3 == 0){
               dp[i] = Integer.min(dp[i], dp[i/3]+1);
           }
        }
        System.out.println(dp[N]);

    }
}

 

📣 comment

이 문제는 DFS로도 풀 수 있는 문제이므로 다시 한 번 풀어보기!