A→B(백준 16953번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?✓

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

---

난이도 체감

1. 최상

2. 상

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

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

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

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

나의 풀이

from collections import deque

A,B=map(int,input().split())

queue=deque()

queue.append((A,1))

while queue:
    v=queue.popleft()
    v1=v[0]*2
    v2=(v[0]*10)+1
    if v1==B or v2==B:
        print(v[1]+1)
        break
    if v1<B:
        queue.append((v1,v[1]+1))
    if v2<B:
        queue.append((v2,v[1]+1))
else:
    print(-1)

• 2를 곱한다. → *2
• 1을 수의 가장 오른쪽에 추가한다. → *10+1
• 위처럼 식을 세울 수 있다. 따라서 BFS방식으로 값을 만들 수 있는지 탐색하도록 코딩하였다. 이 때, 원래 count방식으로 몇번의 계산을 해야 하는지 계산하려고 했는데, 연산을 한번 할 때마다 +1을 더하는 것으로 계산할 수 없었다.(같은 depth를 갖는 node의 계산일 수도 있기 때문)
• 따라서 (연산값, 총 연산 수)의 튜플 형태로 queue에 저장하는 BFS 알고리즘을 사용하였다.

+) while에도 else를 사용할 수 있다.