[BOJ 12852] 1로 만들기 2 (Java)

문제

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

12852번: 1로 만들기 2

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

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

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

 

풀이

DP를 이용하여 풀었다. 

작은 문제들의 답을 구한다.

dp[2] = 1, N이 2일 때는 최소 횟수가 1이다. (2으로 나눔)

dp[3] = 1, N이 3일 때는 최소 횟수가 1이다 (3으로 나눔)

 

N이 4일 때는? 

3으로 나누는 것은 불가능.

2로 나눈다면? 다음 수는 2가 된다. 

1을 뺀다면? 다음 수는 3이 된다. 

연산 1회 + dp[2], dp[3] 중에 최소값 = dp[4]

 

N이 6일 때는?

연산 1회 + (dp[6/3], dp[6/2], dp[6-1])의 최소값 = dp[6] 

이런 식으로 N을 4부터 증가시키면서 N까지 값을 채워나가면 dp[N]을 구할 수 있다.

이후 과정 값은 따로 for문을 하나 더 추가해서 구했다. 

 

소스코드

package dp;

import java.util.Scanner;

public class BOJ12852 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int dp[] = new int[n+1];
        for(int i = 2; i <= n; i++){
            if(i == 2 || i == 3){
                dp[i] = 1;
                continue;
            }
            int min = dp[i-1]+1;
            if(i%3 == 0) min = Math.min(min, dp[i/3]+1);
            if(i%2 == 0) min = Math.min(min, dp[i/2]+1);

            dp[i] = min;
        }

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

        StringBuilder sb = new StringBuilder();
        sb.append(n).append(" ");
        while(n > 1){

            int min = dp[n-1];
            int ans = n-1;
            if(n%3 == 0 && dp[n/3] < min){
                min = dp[n/3];
                ans = n/3;
            }
            if(n%2 == 0 && dp[n/2] < min){
                min = dp[n/2];
                ans = n/2;
            }
            n = ans;
            sb.append(n).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}