BOJ 16953번 : A -> B (Python/Silver 2)

16953번: A → B

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

 

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

 

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

---

예제 입력

2 162

예제 출력

5

---

풀이

 

● 2 -> 162 로 바꿀 때, 거꾸로 가보자.

1) 가능한 연산 중 2를 곱하는 것이 있기 때문에 162를 2로 나누어 보는 것을 생각한다.

2) 2로 나눴을 때 나머지가 0이면 그 수에 2를 곱한 것이다. 그러나 나머지가 0이 아닌 경우 2를 곱한 것이 아니게 된다.

3) 162 % 2 = 0이기 때문에 몫인 81에 2를 곱한 것이 된다. 그러나 81을 다시 2로 나누면 나머지가 1이다. 

4) 2로 곱한 것이 아니게 돼서, 가능한 연산 중 1을 수의 가장 오른쪽에 추가한다는 것을 생각한다. 그렇다면 8에 1을 추가했다는 것을 알 수 있다.

5) 그럼 8에서 1을 빼야 하는데, 여기서 주의할 점이 있다. 문자열로 치환해서 1을 제거하면 좋으나 1이 아닌 다른 숫자가 붙어있다면 처리할 예외 상황은 늘어나고 코드 길이 또한 길어진다.

6) 따라서 3번으로 돌아가서, 81을 2로 나누지 않고 10으로 나눈다. 그럼 81 % 10 = 1, 81 // 10 = 8 이다.

7) 8 // 2 = 4, 4 // 2 = 2 가 됐을 때 정수 A와 같아졌다는 것을 알 수 있다.

Solution

import sys
input = sys.stdin.readline

a, b = map(int,input().split())
cnt = 0

while a < b:
    if b % 2 != 0 and b % 10 != 1: #두 조건이 성립되지 않을 때
        break
    if b % 10 == 1: #홀수일 때 10으로 나누면 1만 남게 됨. 그럼 조건 하나가 성립. 
        b //= 10
        cnt += 1
    elif b % 2 == 0: #짝수일 때 2를 곱한 경우이므로 조건 하나가 성립
        b //= 2
        cnt += 1

if a == b:
    print(cnt + 1)
else:
    print('-1')

 

틀린 코드

import sys
input = sys.stdin.readline

a, b = map(int,input().split())
cnt = 0
while a < b:
    if b % 2 != 0:
        if b <= 10:
            b //= 2
            cnt += 1
        else:
            str_b = str(b)
            b = int(str_b[:-1])
            cnt += 1
    elif b % 2 == 0:
        b //= 2
        cnt += 1

if a == b:
    print(cnt + 1)
else:
    print('-1')

주어졌던 테스트 케이스는 모두 맞았으나 제출 결과는 오답이다.

반례: 2 43

답 : -1
실제 출력 : 3

 

10으로 나눴을 때 나머지가 1이여야만 조건이 성립한다. 그러나 위 코드는 나머지가 1이 아닌 경우까지 포함시켜서 틀린 것이다. 만약 83을 10으로 나눴을 때 나머지가 1이 아닌데도 몫이 4이기 때문에 짝수일 때의 코드로 넘어간다. 그래서 짝수, 홀수로 나누는 게 아닌 10으로 나눴을 때 나머지가 1인 것만 계산하도록 한다.