-
0309_백준 알고리즘 #16953. A -> B알고리즘 2024. 3. 9. 21:36
문제
https://www.acmicpc.net/problem/16953
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
코드
import sys A, B = map(int, sys.stdin.readline().split()) def cal(A, B): cnt = 0 while True: try: if B % 2 == 0: # 짝수인지 확인 n = B // 2 B = B // 2 cnt += 1 elif int(str(B)[-1]) == 1: # 맨 끝자리가 1인지 확인 cnt += 1 length = len(str(B)) n = int(str(B)[:length - 1]) # 1인 부분 절삭 B = n else: return -1 # 가지치기 if n == A: return cnt + 1 except: return -1 print(cal(A, B))
※ 가지치기의 중요성을 깨달은 문제 ! 가지치기 안하고 냈을 때 PyPy에서도 시간 초과 당했는데 가지치기 + readline 추가하고 바로 정답~ 히히 문제는 A -> B 였지만 B -> A로 생각해서 조금 더 빨리 풀 수 있었던거 같기두?
'알고리즘' 카테고리의 다른 글
0311_백준 알고리즘 #17298. 오큰수 (2) 2024.03.11 0310_백준 알고리즘 #1260. DFS와 BFS (0) 2024.03.10 0308_백준 알고리즘 #14501. 퇴사 (0) 2024.03.09 0307_백준 알고리즘 #4673. 셀프 넘버 (0) 2024.03.07 0306_백준 알고리즘 #4779. 칸토어 집합 (0) 2024.03.06