링크

12852 1로 만들기 2

문제

풀이

이 문제는 전에 작성했던 [백준] 1로 만들기 이 문제를 심화하는 느낌이다.

인덱스르 저장할 배열을 하나 더 만든다. 그래서 인덱스 타고 타고 가는 느낌이다

위 사진은 10을 입력했을때고 첫번째 배열이 연산횟수를 저장하는 배열이고
두번째 배열이 1로 가는 길? 이라고 생각하면 된다.
10을 입력하면 10 9 3 1이 최소 연산이다.
두번째 배열을 road라고 가정하고 10을 입력했을 때
road[10] = 9다 그럼 road[9]로 가고 road[9] = 3이다 이런식으로 큐에 넣고 하나하나 넣어주면 된다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n+1];
        int[] visited = new int[n+1];

        dp[1] = 0;

        for(int i=2;i<dp.length;i++){
            dp[i] = dp[i-1] + 1;
            visited[i] = i - 1;

            if(i % 3 == 0) {
                if(dp[i/3] + 1 < dp[i]){
                    dp[i] = dp[i/3] + 1;
                    visited[i] = i/3;
                }
            }

            if(i % 2 == 0) {
                if(dp[i/2] + 1 < dp[i]){
                    dp[i] = dp[i/2] + 1;
                    visited[i] = i/2;
                }
            }


//            System.out.println(Arrays.toString(dp));
//            System.out.println(Arrays.toString(visited));
//            System.out.println("----------------------");

        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);

        if(n == 1){
            System.out.println("0");
            System.out.println("1");
        } else{
            System.out.println(dp[n]);

            while(true){
                n = visited[n];
                queue.add(n);
                if(n == 1) break;
            }

            while(!queue.isEmpty()){
                System.out.print(queue.poll() + " ");
            }
        }


    }


}