[BaekJoon] 백준 16953번 _ A→B for JAVA

 

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

16953번: A → B

 

문제

 

 

---

 

완전 탐색으로 풀었다.

 

어차피 B보다 값이 커지면 멈출거고, A=2, B=10^9이어도 최솟값이 1억보다 작기 때문에 괜찮다고 판단함

 

 

B보다 커지면 Queue에 안넣을거라서 int값으로 했는데 long값으로 해줘야했다. 흠

 

 

코드

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

public class Main {
	static class Node implements Comparable<Node>{
		long value, cnt;
		
		public Node(long value, long cnt) {
			this.value = value;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Node o) {
			return (int) (this.cnt - o.cnt);
		}
	}
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		
		if(A==B) { // 아예 같으면 0
			System.out.println("0");
			return;
		}
		
		PriorityQueue<Node> queue = new PriorityQueue<>();
		queue.offer(new Node(A, 1));
		
		while(!queue.isEmpty()) {
			Node out = queue.poll();
			if(out.value == B) {
				System.out.println(out.cnt);
				return;
			}
			if(out.value * 2 <= B && out.value*2 >= 0) { // 값이 너무 커져서 -값이 될까봐 >=0 조건을 넣어줬음
				queue.offer(new Node(out.value * 2, out.cnt+1));
			}
			if(out.value*10+1 <= B && out.value*10+1 >= 0) {
				queue.offer(new Node(out.value*10+1, out.cnt+1));
			}
		}
		
		System.out.println("-1");
		
	}
}

 

성능

 

 

class 이름을 Node라고 했는데.. 사실 노드는 아니긴 하다.

 

그런데 이름 짓기 힘들어서 그냥 노드라고 함..... 네이밍이 제일 힘들어!!