[백준/파이썬] 16953번 A → B

https://www.acmicpc.net/problem/16953

문제 해석

 

정수 A를 B로 바꾸는 문제이다. 가능한 연산은 2를 곱하거나, 가장 오른쪽에 1을 추가한다.

---

코드

 

input = __import__('sys').stdin.readline
a, b = map(int, input().split())
cnt = 1
# a -> b 가 아닌 b -> a 로 가면서 가능한지 확인
# 즉 2로 나눌수 있다면 나누고, 나눌 수 없는 1 이 있는 경우엔 1을 제거하고 // 10 을 통해 b -> a
# 1이 아닌 홀수가 온다면 만들 수 없음.

while 1:
    # 정답이라면 출력
    if a == b:
        print(cnt)
        exit(0)
    # 1이라면 더이상 답을 구할 수 없으므로 -1
    if b == 1:
        print(-1)
        exit(0)
    
    # 가장 오른쪽에 1이 있다면 1을 제거하고 나누기 10
    if str(b)[-1] == '1':
        b = int(str(b)[0:-1])
    # 짝수라면 나누기 2
    elif b % 2 == 0: b //= 2
    # 1이 아닌 홀수면 불가능
    else: 
        print(-1)
        exit(0)
    cnt += 1

---

문제 풀이

 

1. 처음에는 2진수로 바꾸어 풀려고 해보았는데 가장 오른쪽에 1을 추가하는 방법이 도저히 떠오르지 않았다.

2. 문제의 A->B가 아닌 B->A로 가는 방법을 생각했다.

B에 대해 가장 오른쪽 수가 (1인 경우) 해당 수를 제거하고, 짝수인 경우 2를 나누는 연산을 통해 A를 확인했다.

최종적으로 B의 값이 1이라면 더이상 답을 구할 수 없기 때문에 -1을 출력하도록 해주었다.

즉 2, 162가 주어졌을 때 162는 짝수 이므로 81

81에 가장 오른쪽에 1이 존재하므로 8

8 -> 4

4 -> 2

위 과정을 통해 답을 구할 수 있었다.

 

3. 하지만 1, 163 이 주어졌을 때 즉 1이 아닌 홀수가 주어졌을 때도 가장 우측 값을 제거해 런타임 오류가 났다.

163이 주어지면 16으로 변환되었다.

따라서 1이 아닌 홀수가 존재할 때 -1을 출력하도록 해주었다.