| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 31012 | 12920 | 10350 | 40.177% |
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
답안
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
queue = deque([(n, 1)])
while queue:
num, step = queue.popleft()
if num == m:
print(step)
exit()
elif num > m:
continue
else:
queue.append((num * 2, step + 1))
queue.append((10 * num + 1, step + 1))
print(-1)풀이
A에 2를 곱하고, 1을 오른쪽에 추가하는 연산을 하는 모든 경우의 수를 구하는 코드이다.
A에 2를 곱하는 연산은 a * 2로, 오른쪽에 추가하는 연산은 10 * a + 1을 통해 가능하다.
위 코드에서는 연산을 하는 모든 경우의 수를 구하되,
- 만약 연산 결과가 B와 같으면 연산의 횟수를 출력한 뒤 프로그램을 종료하고,
- 연산 결과가 B보다 크면 그 수에 어떤 연산을 하더라도 B가 될 수 없으므로 그 수에 연산을 하는 것을 중단하고,
- 연산 결과가 B보다 작으면 그 수에 두 가지의 연산을 수행한다.
하지만 이것을 재귀 등으로 구현한다면, 연산의 최솟값이 예를 들어 3일 경우에도 4, 5, 6, … 번 연산하는 경우의 수를 구함으로써 필요 없는 계산을 할 수도 있다.
그것을 방지하기 위해 나는 queue를 도입했다.
queue 안에 있는 튜플 첫 번째 요소는 문제의 주어진 숫자인 A를 나타내고, 두 번째 요소는 그 숫자를 얻기 위해 수행한 연산의 횟수를 나타내는데,
위 답안에서는 queue를 통해 연산의 횟수(step)가 n-1인 연산이 모두 끝나야만 연산의 횟수가 n인 연산이 수행되도록 했다.
이예찬