백준 16953 - 파이썬

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

16953번: A → B

 

문제 풀이

처음에 이 문제를 봤을 때 떠오른 아이디어는 bottom up 방식으로 푸는것보다 top down 방식으로 푸는게 훨씬 빠르겠다는 생각이 들었다. 그래서 162 -> 81 -> 8 -> 4 -> 2 이런식으로 해결해 보았다.

 

x, y = map(int, input().split())

result = 1

while y != x:
  temp = y
  result +=1
 
  if y % 10 == 1:
    y //= 10

  elif y % 2 == 0:
    y //= 2

  if temp == y:
    print(-1)
    break

print(result)

그런데 이렇게 해보니 결과는 틀렸다고 나왔다. 왜 그런지 고민해 보다가 해결책을 찾지 못해서 다른 사람의 풀이를 찾아 보았다. 이 분의 풀이에는 temp라는 변수가 나와 다른 점이었는데, 이 변수에 계산되기 이전의 y값을 넣어 맨 마지막에 비교하여 서로 같은 값이 나올 경우 while문을 탈출하지 못 하였다는 것이기 때문에 -1이 출력되도록 하였다. 이 점이 나와 다른 점이었던거 같다.

 

x,y = map(int,input().split())

result = 1

while y != x:
    result+=1
    temp = y
    if y%10 == 1:
        y//=10
    elif y%2 == 0:
        y//=2
    
    if temp == y:
        print(-1)
        break
else:
    print(result)

구글링을 하다가 큐를 사용하여 푼 코드도 찾아보았다.

BFS를 이용한 방식이다.

from collections import deque

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

res = -1
que = deque([(a,1)])

while que:
  i, cnt = que.popleft()

  if i == b:
    res = cnt
    break

  if i*2 <= b:
    que.append((i*2, cnt+1))
  if int(str(i) + '1') <= b:
    que.append((int(str(i) + '1'), cnt+1))

print(res)

2 162
deque([(2, 1)])
deque([(4, 2), (21, 2)])
deque([(21, 2), (8, 3), (41, 3)])
deque([(8, 3), (41, 3), (42, 3)])
deque([(41, 3), (42, 3), (16, 4), (81, 4)])
deque([(42, 3), (16, 4), (81, 4), (82, 4)])
deque([(16, 4), (81, 4), (82, 4), (84, 4)])
deque([(81, 4), (82, 4), (84, 4), (32, 5), (161, 5)])
deque([(82, 4), (84, 4), (32, 5), (161, 5), (162, 5)])
deque([(84, 4), (32, 5), (161, 5), (162, 5)])
deque([(32, 5), (161, 5), (162, 5)])
deque([(161, 5), (162, 5), (64, 6)])
deque([(162, 5), (64, 6)])
5

 

deque에 값이 들어가는 것을 출력해보면 위와 같다. 

if i*2 <= b:
    que.append((i*2, cnt+1))
  if int(str(i) + '1') <= b:
    que.append((int(str(i) + '1'), cnt+1))

이 부분이 핵심인데 2를 곱하는 경우와 맨 뒤에 1을 추가하는 경우의 수를 모두 큐에 추가하여 구하는 방식이다.

 

또 다른 방식으로는 heapq를 이용하여 구현한 방식도 있다.

import sys
import heapq

input = sys.stdin.readline

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

def mulTwo(a, count):
  return count+1, a*2

def addOne(a, count):
  return count+1, int(str(a) +'1')

def solution(a, b):
  q = [(0, a)]
  while q:
    print(q)
    cnt, a = heapq.heappop(q)
    if a<b:
      heapq.heappush(q, mulTwo(a, cnt))
      heapq.heappush(q, addOne(a, cnt))

    elif a == b:
      return cnt+1
    else:
      continue

  return -1

print(solution(a,b))

heap에 추가되는 순서대로 출력해보면 다음과 같다.

 

[(0, 2)]
[(1, 4), (1, 21)]
[(1, 21), (2, 8), (2, 41)]
[(2, 8), (2, 41), (2, 42), (2, 211)]
[(2, 41), (2, 211), (2, 42), (3, 16), (3, 81)]
[(2, 42), (2, 211), (3, 81), (3, 16), (3, 82), (3, 411)]
[(2, 211), (3, 16), (3, 81), (3, 411), (3, 82), (3, 84), (3, 421)]
[(3, 16), (3, 82), (3, 81), (3, 411), (3, 421), (3, 84)]
[(3, 81), (3, 82), (3, 84), (3, 411), (3, 421), (4, 32), (4, 161)]
[(3, 82), (3, 411), (3, 84), (4, 161), (3, 421), (4, 32), (4, 162), (4, 811)]
[(3, 84), (3, 411), (4, 32), (4, 161), (3, 421), (4, 811), (4, 162), (4, 164), (4, 821)]
[(3, 411), (3, 421), (4, 32), (4, 161), (4, 821), (4, 811), (4, 162), (4, 164), (4, 168), (4, 841)]
[(3, 421), (4, 161), (4, 32), (4, 164), (4, 821), (4, 811), (4, 162), (4, 841), (4, 168)]
[(4, 32), (4, 161), (4, 162), (4, 164), (4, 821), (4, 811), (4, 168), (4, 841)]
[(4, 161), (4, 164), (4, 162), (4, 841), (4, 821), (4, 811), (4, 168), (5, 64), (5, 321)]
[(4, 162), (4, 164), (4, 168), (4, 841), (4, 821), (4, 811), (5, 321), (5, 64), (5, 322), (5, 1611)]

 

이처럼 계속 맨 왼쪽에 있는 값을 꺼내어 확인 후 b의 값과 일치하면 해당 힙에 같이 저장되어 있던 카운트를 출력해주는 원리이다.

 

이 문제를 풀면서 느낀 점은 맨 첨에 top dwon 방식으로 풀면서 정답을 거의 가까이 유추하였지만 반복문 탈출하는 방식을 생각하지 못한 점이 아쉽다. 또한 한 가지 답을 구하는데 있어 정말 여러가지 풀이 방식이 존재한다는 것이다. 따라서 풀었다고 다음 문제로 넘어가는 것이 아닌 다른 풀이는 없는지 찾아보면서 견식을 확장하는것이 중요한거 같다.