[백준]12852번. 1로 만들기 2(JAVA)

문제

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

---

풀이

import java.io.*;
import java.util.*;

public class Main {


    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        int[] dp = new int[n+1];
        if(n < 4){
            dp = new int[4];
        }

        HashMap<Integer, List<Integer>> map = new HashMap<>();
        dp[1] = 0;
        map.put(1, new ArrayList<>(Arrays.asList(1)));
        dp[2] = 1;
        map.put(2, new ArrayList<>(Arrays.asList(1, 2)));
        dp[3] = 1;
        map.put(3, new ArrayList<>(Arrays.asList(1, 3)));
        if(n >= 4){
            for(int i = 4; i < n+1; i++){
                int minIdx = i-1;
                int min = dp[i-1] + 1;
                if(i % 3 == 0){
                    int temp = dp[i/3] + 1;
                    if(min > temp){
                        min = temp;
                        minIdx = i/3;
                    }
                }
                if(i % 2 == 0){
                    int temp = dp[i/2] + 1;
                    if(min > temp){
                        min = temp;
                        minIdx = i/2;
                    }
                }
                dp[i] = min;
                map.put(i, new ArrayList<>()); // i에 빈 리스트를 할당
                map.get(i).add(i); // i 리스트에 i 값 추가
                map.get(i).addAll(map.get(minIdx)); // minIdx의 리스트 값을 모두 i 리스트에 추가
            }
        }
        System.out.println(dp[n]);
        Collections.sort(map.get(n), Collections.reverseOrder());
        for(int i : map.get(n)){
            System.out.print(i + " ");
        }

    }

}

n 이 작을 경우를 대비해서 초기값을 넣어준다.

이후 -1한 경우, /2 인 경우, /3인 경우에 대해 이 전의 값 +1 이 제일 작은 값을 추적하여 기록한다.

최종적으로 오름차순으로 정렬하여 출력한다.