오늘 문제도 은근히 그리디 알고리즘에서 자주 보이는 유형의 문제입니다. 살펴볼까요?
1. 오늘의 학습 키워드
- 그리디 알고리즘
2. 문제: 16953. A → B
- 단계: 🥈 실버 2단계
- 주제:
- 출처: https://www.acmicpc.net/problem/16953
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
예제 입력 1 복사
2 162
예제 출력 1 복사
5
2 → 4 → 8 → 81 → 162
예제 입력 2 복사
4 42
예제 출력 2 복사
-1
예제 입력 3 복사
100 40021
예제 출력 3 복사
5
100 → 200 → 2001 → 4002 → 40021
3. 문제 풀이
Step1. 문제 이해하기
해당 문제는 정수 A를 B로 바꾸는데 필요한 연산의 최솟값을 구하는 문제입니다.
연산은 다음과 같이 두 가지가 있습니다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
입출력을 살펴보겠습니다.
- Input: A와 B가 주어집니다. 1이상 이하라는 것은 int형 중 자연수들이라는 것을 알 수 있습니다.
- Output: A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력합니다. 만들 수 없는 경우에는 -1을 출력합니다.
Step2. 문제 분석하기
A에서 B로 변환하는 과정을 생각하면 경우의 수가 매우 많아집니다. 왜냐하면 연산은 두 가지 이기 때문에 만큼 수가 늘어납니다.
하지만 반대로 B에서 A로 변환하면, 다음 두 가지 연산을 특정 조건에 따라 1번씩 적용하면 됩니다.
- B가 짝수인 경우, 2로 나누는 연산 수행.
- B의 마지막 자리가 1인경우, 즉 10으로 나누었을 때 나머지가 1인 경우, 마지막 숫자 1을 제거
위 연산을 반복하면서 B가 A로 줄어드는 과정을 시뮬레이션하면 됩니다.
따라서, B에서 A로 접근하면 현재 상태에서 가능한 연산 중 하나를 적용하여 문제를 해결할 수 있습니다. 이는 탐욕적 선택을 가능하게 하며, 최적의 결과를 보장합니다.
바로 코드 설계를 해보도록 하겠습니다.
Step3. 코드 설계
- B가 A보다 작아지면 연산을 종료
- B의 마지막 자리가 1인 경우(B를 10으로 나누었을 때 나머지가 1인 경우), B를 10으로 나눕니다.
- B가 짝수인 경우, B를 2로 나눕니다.
- 위 두 가지 연산을 수행하지 못한다면 A로 변환할 수 없는 것이기 때문에 바로 -1을 반환합니다.
Step4. 코드 구현
import sys
A, B = map(int, sys.stdin.readline().split())
def sol(a, b):
cnt = 0
while b > a:
cnt += 1
if b % 10 == 1:
b //= 10
elif b % 2 == 0:
b //= 2
else:
return -1
return cnt + 1 if b == a else -1
print(sol(a=A, b=B))- 시간 복잡도:
- B에서 A로 변환하면서 B를 반으로 줄이거나 자릿수를 하나씩 제거합니다.
- B가 A로 수렴하는 동안 연산 횟수는 에 비례합니다.
- 입력 조건에서 , 최악의 경우 여도 충분히 여유가 있습니다.
- 결과:
4. 마무리
이 문제는 변환 과정을 역순으로 생각하면 그리디하게 접근할 수 있습니다. 작은 단계에서 최적의 선택(2로 나누거나 마지막 숫자를 제거)을 반복하여 최종 결과를 도출할 수 있습니다. 해당 문제는 BFS로도 풀 수 있는데 이 내용은 추후에 BFS문제들을 풀 때 다시 돌아오도록 하겠습니다!!
읽어주셔서 감사합니다.
어제보다 나은 오늘, 오늘보다 나은 내일!!
