💯Problem Solving
[BOJ] 16953 A→B
date
Jul 7, 2023
slug
boj-16953
author
status
Public
tags
Python
BOJ
summary
백준 16953번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Nov 3, 2024 11:22 AM
문제 링크
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
문제풀이
예제에 있는 2 → 162로 바꾸는 방법이다.
가능한 방법은 2가지, A에 2를 곱하거나, 뒤에 1을 더하거나인데,
트리구조로 왼쪽 자식은 2를 곱하는것, 오른쪽 자식은 뒤에 1을 더하는것으로 구조를 짜면
BFS로 진행할 수 있다.
목표하는 B값보다 크면 Queue에 넣지 않고
만약 B값과 같으면 그 노드의 깊이를 반환하면 된다
파이썬 문제풀이 코드
from collections import deque arr = deque() A, B = tuple(map(int, input().split())) arr.append((A, 1)) while True: if not len(arr): print(-1) break number, depth = arr.popleft() # print(number, depth) if number > B: continue if number == B: print(depth) break arr.append((2*number, depth+1)) arr.append((10*number+1, depth+1))
시간복잡도
- O(log2^N)
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.