백준 1463번 1로 만들기 (자바) 풀이

문제

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

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

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

 

입력

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

출력

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

예제 입력 1 복사

2

예제 출력 1 복사

1

예제 입력 2 복사

10

예제 출력 2 복사

3

풀이

 

해당 문제또한 마찬가지로 다이나믹 프로그래밍을 활용하여 풀이하는 문제이다.

 

해당 문제에서 제시하는 기본 조건은 3가지로, 가장 신경써야할것은 X를 최소한의 횟수로 1을 만들어야한다는 것이다.

 

예로, 제시된 예제가 10을 입력했을때 3을 반환해야한다는 것인데, 아무런 생각 없이 구현한다면 4의 결과값이 나오게 된다.

 

 

        int[] dp = new int[N+1];
        dp[0] =0;
        dp[1] =0;

마찬가지로 배열을 생성해 N까지 경우의수를 탐색한다.

그리고 이미 제시가 되어있는 값은 입력한다. 0과 1을 입력하면 어떠한 연산도 하지 않기때문에 횟수는 0이 된다.

 

        for(int i=2; i<=N;i++){
            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);
            }
        }

그리고 마찬가지로 2부터 문제를 풀어나가기 위해 반복문을 선언한다.

 

단순히 10까지의 최소 연산 횟수를 구한다고 치면,

• 0 = 0
• 1 = 0
• 2 = 1 (2-1)
• 3 = 1 (3/3)
• 4 = 2 (4/2/2)
• 5 = 3 ((5-1)/2/2)
• 6 = 2 (6/3/2)
• 7 = 3 ((7-1)/3/2)
• 8 = 3 (8/2/2/2)
• 9 = 2 (9/3/3)
• 10 = 3 ((10-1)/3/3)

 

이렇게 봤을때 느낄 수 있는건, 원래 단순히 최저 횟수를 생각하지 않고 계산을 했을때 , 생각하고 계산했을때의 횟수를 비교해야 된다는 것이다.

위의 연산을 배열로 표현해본다면

• dp[2] = dp[2-1]+1 혹은 dp[2] = dp[2/2]+1
• dp[3] = dp[3/3]+1
• dp[4] = dp[4-1]+1 혹은 dp[4/2]+1 
• dp[5] = dp[5-1]+1 
• dp[6] = dp[6/3]+1 
• dp[7]= dp[7-1]+1 
• dp[8] = dp[8/2]+1
• dp[9] = dp[9/3]+1
• dp[10] = dp[10-1]+1 혹은 dp[10/2]+1

이렇게 구할 수 있다.

혹은 <이 한번씩 등장한다.

그래서 기본 횟수로 dp[i-1]+1 를 값으로 넣어주고, 비교를 해서 더 작은 값을 넣어주는것이다.

 

다이나믹 프로그래밍을 구현할때는 어떠한 값을 구한다기 보다는 정말 구해야되는 답을 위해서 편법을 쓴다는 생각으로 풀이해야하는것 같다..

package baekjoon.a1463;

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

public class a1463 {
    public static int count =0;
    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[0] =0;
        dp[1] =0;
        for(int i=2; i<=N;i++){
            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]);
    }
}