[Silver1] No.16953 A -> B
20 Apr 2022A -> B
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
문제 풀이
생각보다 너무 쉽게 풀려 당황했기 때문에 두가지 방법을 찾아서 풀어 보았다.
두가지 방법이 있다.
- 모든 예외 처리를 추가해 거꾸로 B 에서 A로 추적하는 방법
- BFS나 DFS를 이용해 A가 B가 될때까지 수를 구해주면 된다.
1. 예외처리
먼저 첫번째 방법은 A에서 B로 가는데는 2를 곱하거나, 뒤에 1이 붙거나 두가지 방법밖에 없다.
따라서, B에서 A로 가면서 2로 나누어지는 짝수일경우, 또는 10으로 나누었을 때 나머지가 1이 나오는경우만 판별하여 A까지 가는 최솟값을 구해주면 된다.
여기서 주의할 점은 저 두가지 경우의 수 외에 [ 3 5 6 7 9 ] 와같은 숫자로 끝날 경우 위에서 제시한 두가지의 연산 방법으로는 도출할수 없는 수이기 때문에 그냥 -1로 반환해준다.
2. BFS, DFS
BFS에서 그리디 알고리즘을 이용해 A에서 B까지 가는 두가지 연산
- A * 2
- A * 10 + 1
이 B보다 크지 않을경우에 한에 Queue에 넣어주면서 전체적으로 탐색해 주면된다.
그러다 B와 같은 숫자가 있을 경우에만 연산의 최솟값을 반환하고, 나머지는 -1을 반환 해주면된다.
여기서 주의할 점은 B의 값이 10⁹ * 10 + 1의 연산이 들어갈 수 있으니, A의 값을 계산하는 변수는 int의 범위를 넘어갈 수 있다. 그러므로 long의 원시타입을 사용해 풀이해 준다.