백준 12852(JAVA)

문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

풀이

dp로 풀면 시간초과가 나지않을수 있다.
일단 현재 어떠한 수를 i(1 과 입력되는 N사이의 임의의 수)
라 하면 i의 연산의 최소횟수는 i - 1 수의 연산의 최소횟수, i / 3(나머지가 0이라면) 수의 연산의 최소횟수, i / 2(나머지가 0이라면) 수의 연산의 최소횟수의 의 가장 작은 값에 + 1을 한것이다.

그리고 연산되는 방법의 수는 List<List<Integer>> list = new ArrayList<>();로 List의 원소로 List를 갖게하여 i에 대해서 i - 1, i / 2, i / 3의 최소 연산횟수의 수의 방법의 수를 넣는 방법으로 찾았다.

코드

package baekjoon.DP;

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main12852 {
    static int N;
    static int[] d = new int[1000001];
    static List<List<Integer>> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        N = Integer.parseInt(br.readLine());
        for(int i = 0; i < N + 1; i++) list.add(new ArrayList<>());
        list.get(1).add(1);
        dpSolve();

        bw.write(d[N]+"\n");
        Collections.sort(list.get(N), Comparator.reverseOrder());
        for (Integer integer : list.get(N)) {
            bw.write(integer + " ");
        }

        bw.flush();
        bw.close();
    }
    static void dpSolve(){

        for(int i = 2; i <= N; i++){
            d[i] = d[i - 1] + 1;
            boolean isDivided1 = false;
            boolean isDivided2 = false;

            if(i % 3 == 0 && d[i] > d[i / 3] + 1){
                isDivided1 = true;
                d[i] = d[i / 3] + 1;

            }
            if(i % 2 == 0 && d[i] > d[i / 2] + 1){
                isDivided2 = true;
                d[i] = d[i / 2] + 1;

            }
            if(isDivided2 && !isDivided1){
                for (Integer v : list.get(i / 2)) {
                    list.get(i).add(v);
                }
            }else if(isDivided1 && !isDivided2){
                for (Integer v : list.get(i / 3)) {
                    list.get(i).add(v);
                }
            }else if(!isDivided1 && !isDivided2){
                for (Integer v : list.get(i - 1)) {
                    list.get(i).add(v);
                }
            }
            list.get(i).add(i); // 결과도 넣어야함.
        }
    }
}

/**
 * 현재 i수에 대해서 i - 1 + 1과
 * i / 2 + 1의 횟수와
 * i / 3 + 1의 횟수를 비교하면 된다.
 * dp테이블의 값은 연산의 횟수를 저장하고
 * 바텀업으로 2부터 입력되는 N까지의 수에 대해서 메모이제이션을하자
 * 연산의 방법의 수는 list에 저장하여품
 */