0309. [BOJ#16953] A → B

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

16953번: A → B

2 초

512 MB

51014

20978

16660

39.620%

문제

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

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

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

입력

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

출력

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

---

제출 코드

import sys
sys.setrecursionlimit(10**6)

def recur(num, cnt):
    global ans, cnt2
    
    if num == B:
        ans = B
        cnt2 = cnt
        return cnt
    if num > B:
        return cnt

    double(num, cnt)
    front_one(num, cnt)

def double(num, cnt):
    global ans
    if num == B:
        ans = B
        return cnt
    if num > B:
        return cnt
    
    num = num * 2
    cnt += 1
    recur(num, cnt)

def front_one(num, cnt):
    global ans
    if num == B:
        ans = B
        return cnt
    if num > B:
        return cnt
    
    num = str(num) + '1' # 뒤에 1을 붙임
    num = int(num) # 정수로 변환
    cnt += 1
    recur(num, cnt)

ans = -1
cnt2= 0
A, B = map(int, input().split())
result = recur(A, 1)
if ans == B:
    print(cnt2)
else:
    print(ans)

 

문제가 컴팩트해서 구현쪽만 신경쓰면 됐던 문제.

갈래를 나누는 함수를 만들어두고 연산을하는 두 개의 함수로, 조건을 만족한다면 진행하는 식으로 했다.

결과값이 나올 수 있을 때, 리턴값으로 cnt를 받아서 나오고 싶었지만, 실력이 부족해서 변수를 하나 더 할당해서 나타냈다.

요즘 문제를 풀면서 느끼지만 다른 풀이법도 많이 알아보고 사용해보는 습관을 길러야 할 것 같다.