[동적 계획법] 백준 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[N] : 정수가 N를 1로 만들 때 연산을 사용하는 횟수의 최솟값

trace[] : 연산을 사용했을 때 그 전의 값을 저장하는 배열

 

점화식 찾기

• 3으로 나누기 dp[6] = dp[2]+1 = dp[i/3]+1
• 2로 나누기 dp[6] = dp[3]+1 = dp[i/2]+1
• 1을 빼기 dp[6] = dp[5]+1 = dp[i-1]+1

중 최솟값 저장해주고 해당 연산 결과값을 배열trace에도 경로를 저장해준다.

 

예를 들어 N=10일 때,

• 1을 빼기 dp[10] = dp[9] + 1 = 3으로 최솟값 ➔ 9를 trace[10]에 저장해준다
• 2로 나누기 dp[10] = dp[5] + 1 = 4 
• 3으로 나누기  3으로 나눠지지않음

 

초기값 정의

dp[0] = dp[1] = 0

 

💻 코드

package BOJ;

import java.util.Scanner;

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

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

        dp[0] = dp[1] = 0;
        for(int i=2; i<=N; i++){
            dp[i] = dp[i-1]+1;
            trace[i] = i-1;
            if(i%2==0 && dp[i]>dp[i/2]+1){
                dp[i] = dp[i/2]+1;
                trace[i] = i/2;
            }
            if(i%3==0 && dp[i]>dp[i/3]+1){
                dp[i] = dp[i/3]+1;
                trace[i] = i/3;
            }
        }
        System.out.println(dp[N]);

        StringBuilder sb = new StringBuilder();
        while(N>0){
            sb.append(N+ " ");
            N = trace[N];
        }
        System.out.println(sb);

    }
}