알고리즘/자바
[백준 알고리즘] 16935번 자바(Java) A → B
문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 풀이 처음에 생각했던 방식은 DP(다이나믹 프로그래밍)이었다. 하지만 메모리를 생각했을때 10억이란 숫자는 512MB(1MB당 약 25만개의 정수 담을수있음)이상이 필요하고 그러면 제한조건에 걸리게 된다. 따라서 방법을 변경해야하는데 생각해낸게 BFS이다. 주어진 수가 1만개이고 BFS는 시간복잡도가 O(log n)이기 때문에 제한시간안에 ..
