풀이

아이디어

간단하게 BFS로 풀 수 있는 문제라고 생각합니다.

하지만 다른 풀이로 데이크스트라로 문제를 풀어보도록 해보겠습니다.

가장 맨 처음에 있는 위치 N을 기준으로 -1, +1 로 가는 경우의 가중치는 1입니다.
두배로 가는 경우의 가중치는 0입니다.

이것을 기분으로 문제를 풀어봅시다.

(N,0)을 우선순위 큐에 넣습니다.

이제 (N-1, 1), (N+1, 1), (2 * N, 0)을 큐에 넣습니다.

다만 다익스트라이기 때문에 거리가 갱신된 경우만 큐에 넣습니다!

그렇게 해서 모든 노드들간의 최소 거리를 구했다면 이제 K 노드로 가는 최소 거리를 구해주면 문제를 해결합니다.

상세 구현

다익스트라 문제를 풀기 위해서는 거리 배열, 우선순위 큐가 필요합니다!

각 노드에 대한 거리를 기록하기 위하여 배열을 최댓값으로 초기화하여 선언합니다.

		dist = new int[100_001];
		Arrays.fill(dist, 100_000);
        // 시작점의 거리는 0
		dist[N] = 0;

이제 우선순위큐를 선언하고 거기에 N을 넣어줍니다.

		PriorityQueue<Node13549> pq = new PriorityQueue<>();
		pq.add(new Node13549(N, 0));

이제 3가지 경우(+1, -1, *2)에 대해서 가장 최소로 가는 길을 탐색합니다.

		while(!pq.isEmpty()) {
			Node13549 cur = pq.poll();
			
			if(dist[cur.idx] < cur.dist)
				continue;
			
			if(cur.idx - 1 >= 0 && dist[cur.idx-1] > cur.dist + 1) {
				dist[cur.idx - 1] = cur.dist + 1;
				pq.add(new Node13549(cur.idx-1, cur.dist + 1));
			}
			
			if(cur.idx + 1 <= 100_000 && dist[cur.idx + 1] > cur.dist + 1) {
				dist[cur.idx + 1] = cur.dist + 1;
				pq.add(new Node13549(cur.idx+1, cur.dist + 1));
			}
			
			if(cur.idx * 2 <= 100_000 && dist[cur.idx * 2] > cur.dist) {
				dist[cur.idx * 2] = cur.dist;
				pq.add(new Node13549(cur.idx*2, cur.dist));
			}
		}

이를 통해 우리는 원하는 답인 dist[K]를 구할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class No13549 {
	static int N, K;
	static int[] dist;
	public static void main(String[] args) throws IOException {
		input();
		pro();
	}
	private static void pro() {
		dijkstra();
		System.out.println(dist[K]);
	}
	
	private static void dijkstra() {
		dist = new int[100_001];
		Arrays.fill(dist, 100_000);
		dist[N] = 0;
		
		PriorityQueue<Node13549> pq = new PriorityQueue<>();
		
		pq.add(new Node13549(N, 0));
		
		while(!pq.isEmpty()) {
			Node13549 cur = pq.poll();
			
			if(dist[cur.idx] < cur.dist)
				continue;
			
			if(cur.idx - 1 >= 0 && dist[cur.idx-1] > cur.dist + 1) {
				dist[cur.idx - 1] = cur.dist + 1;
				pq.add(new Node13549(cur.idx-1, cur.dist + 1));
			}
			
			if(cur.idx + 1 <= 100_000 && dist[cur.idx + 1] > cur.dist + 1) {
				dist[cur.idx + 1] = cur.dist + 1;
				pq.add(new Node13549(cur.idx+1, cur.dist + 1));
			}
			
			if(cur.idx * 2 <= 100_000 && dist[cur.idx * 2] > cur.dist) {
				dist[cur.idx * 2] = cur.dist;
				pq.add(new Node13549(cur.idx*2, cur.dist));
			}
		}
	}
	
	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		br.close();
	}
}
class Node13549 implements Comparable<Node13549> {
	int idx;
	int dist;
	
	public Node13549(int idx, int dist) {
		this.idx = idx;
		this.dist = dist;
	}
	
	@Override
	public int compareTo(Node13549 o) {
		return this.dist - o.dist;
	}
}