[JAVA]백준 12852번: 1로 만들기 2

www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

 

1. 문제 설명

 

정수 X에 사용할 수 있는 연산이 3가지가 있다.

 

X/2, X/3, X-1

 

위의 세가지 연산을 사용하여 주어진 정수 N을 1로 만들려고 할 때 연산을 사용하는 횟수의 최솟값과 1로 만드는 방법을 출력하는 문제이다.

 

2. 풀이

 

DP를 이용해서 최솟값을 구하고 그 순간들의 선택을 배열로 저장하여 역추적할 수 있다.

 

dp 배열에는 현재 정수 N을 1로 만들 수 있는 최솟값을 저장하고 trace 배열에는 연산을 사용하였을 때 N 전의 값이 무엇인지 저장한다.

 

X/3 연산을 사용하여 연산 횟수의 최솟값을 구하였다면 trace 배열에는 N/3 값이 저장된다.

 

N까지 dp를 이용하여 최솟값을 구하고 trace 배열을 사용하여 N 부터 역추적하여 출력하면 된다.

 

 

 

 

3. 코드

import java.io.*;

public class Main {




    public static void main(String[] args) throws IOException {

        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));


        int N=Integer.parseInt(br.readLine());

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

        dp[1]=0;
        trace[1]=-1;


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

            if(x%2==0 && dp[x]>dp[x/2]+1){
                dp[x]=dp[x/2]+1;
                trace[x]=x/2;
            }

            if(x%3==0 && dp[x]>dp[x/3]+1){
                dp[x]=dp[x/3]+1;
                trace[x]=x/3;
            }

        }

        int num=dp[N];

        bw.write(String.valueOf(num)+"\n");

        int index=N;

        for(int x=0;x<=num;x++){
            bw.write(String.valueOf(index)+" ");
            index=trace[index];
        }

        bw.flush();
        bw.close();
        br.close();
    }


}