[백준] 16953번 - Silver 2 A -> B, 파이썬 코드

solved.ac의 Class 4 문제 중 A → B 문제이다.

문제 조건

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

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

A를 B로 바꾸는데 필요한 연산의 최솟값을 구하는 문제이다.

dfs를 사용하되, 인자로 현재 계산값과 연산의 횟수를 인수로 가지고 있어야 한다고 생각하고 문제를 풀었다.

즉, (2를 곱한 값과 현재 연산 횟수+1)와, (10를 곱하고 +1 한 값과 현재 연산 횟수+1)을 인수로 주면서 각각 재귀함수를 하면 된다고 생각하고 문제를 풀었다.

 

해결했던 코드는 다음과 같다.

import sys

global a, b
result = []

def dfs(n, cnt):
    # n의 값이 b보다 커졌을 경우는 더 이상 진행 X
    if n > b:
        return
    # n = b인 경우, result 리스트에 추가하기
    if n == b:
        result.append(cnt+1)
        return
    dfs(2*n, cnt+1) # 2를 곱하기
    dfs(n*10+1, cnt+1) # 1을 수의 가장 오른쪽에 추가하기

if __name__ == '__main__':
    a, b = map(int, sys.stdin.readline().split())
    dfs(a, 0)
    if result:
        print(min(result)) # 만들 수 있다면, result 리스트에서 최솟값을 출력
    else:
        print(-1) # 만들 수 없는 경우