목록너비우선탐색 (1)

AtraFelis's Develop Diary

[백준] 16953 - A → B (JAVA)

문제정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.2를 곱한다.1을 수의 가장 오른쪽에 추가한다.A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.입력첫째 줄에 A, B (1≤A출력A를B로바꾸는데필요한연산의최솟값에1을더한값을출력한다.만들수없는경우에는−1을출력한다.풀이BFS를이용하여최소연산횟수를찾는문제이다.주의할것은B의최댓값이10^9이므로,오버플로우가일어날수있다는것이다.첫번째연산인num \times 2일때는int의최댓값인2^{31}-1$을 초과하지 않지만, 두 번째 연산에서는 오버플로우가 일어날 수 있으므로 64bit 자료형인 long을 사용하거나, unsigned int를 사용해야 한다. 하지만..
Algorithm/백준 2024. 5. 14. 18:57
이전 Prev 1 Next 다음