[백준, 자바, 1463번] 1로 만들기

풀이

• 뭔가 시간 제한이 짧아서 걱정했지만,
• 간단히 해결 가능했음.
• 우선 bfs처럼 deque에 추가하기 전에 추가할 값에 해당하는 li의 index를 변경 후 추가
• 이렇게 함으로써 같은 걸, 추가하지 않고 빠르게 해결하고자 했음.

 

import java.util.*;

public class _1463 {
    static Deque<List<Integer>> dq = new ArrayDeque<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        boolean[] li = new boolean[N+1];
        dq.add(new ArrayList<>(Arrays.asList(N,0)));
        li[N] = true;

        while (!dq.isEmpty()) {
            List<Integer> now = dq.pollFirst();
            if (now.get(0)==1) {
                System.out.println(now.get(1));
                break;
            }
            if (now.get(0)%3==0 && !li[now.get(0)/3]) {
                li[now.get(0)/3] = true;
                dq.add(new ArrayList<>(Arrays.asList(now.get(0)/3,now.get(1)+1)));
            } if (now.get(0)%2==0 && !li[now.get(0)/2]) {
                li[now.get(0)/2] = true;
                dq.add(new ArrayList<>(Arrays.asList(now.get(0)/2,now.get(1)+1)));
            } if (now.get(0)-1>0 && !li[now.get(0)-1]) {
                li[now.get(0)-1] = true;
                dq.add(new ArrayList<>(Arrays.asList(now.get(0)-1,now.get(1)+1)));
            }
        }
    }
}