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

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

DP를 풀어보고 싶어서 DP문제집을 들어가서 찾은 문제이다.

너무 BFS 처럼 생겨서 BFS로 풀어버렸다. ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solved12852 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int target = par(br.readLine());
        Queue<Make1> q = new LinkedList<>();
        Make1 start = new Make1(target,0);
        start.list.add(target);
        q.offer(start);
        boolean[] visited = new boolean[target+1];
        while(!q.isEmpty()){
            Make1 poll = q.poll();
            if(visited[poll.value])continue;
            visited[poll.value] = true;
            if(poll.value==1){
                System.out.println(poll.count);
                for (int i = 0; i < poll.list.size(); i++) {
                    System.out.print(poll.list.get(i));
                    if(i!=poll.list.size()-1) System.out.print(" ");
                }
                return;
            }
            if(poll.value%3==0){
                Make1 offer = new Make1(poll.value/3,poll.count+1);
                offer.list.addAll(poll.list);
                offer.list.add(offer.value);
                if(!visited[offer.value])q.offer(offer);
            }
            if(poll.value%2==0){
                Make1 offer = new Make1(poll.value/2,poll.count+1);
                offer.list.addAll(poll.list);
                offer.list.add(offer.value);
                if(!visited[offer.value])q.offer(offer);
            }
            Make1 offer = new Make1(poll.value-1,poll.count+1);
            offer.list.addAll(poll.list);
            offer.list.add(offer.value);
            if(!visited[offer.value])q.offer(offer);
        }
    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}
class Make1{
    int value;
    int count;
    List<Integer> list = new ArrayList<>();
    Make1(int value, int count){
        this.value = value;
        this.count = count;
    }
}