96. 백준 16953 번 파이썬 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그리디 알고리즘 문제인 BOJ 16953 번 A → B 입니다.

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

16953번: A → B

 

먼저 백준 16953 번 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

import sys
input = sys.stdin.readline
A, B = map(int, input().split())
cnt = 1

while A != B:
    cnt += 1
    if B % 10 == 1:
        B = B//10
    elif B % 2 == 0:
        B = B//2
    else:
        cnt = -1
        break
    if B == 0:
        cnt = -1
        break

print(cnt)

 

문제 요약

 

숫자 A 에 2 또는 가장 마지막 자리에 1을 붙여서 B로 최소 횟수 + 1을 출력

만약 불가능하다면 -1 출력

 

문제 접근

A의 마지막 자리에 1을 붙이는 건 어려우므로

B의 마지막 자리에서 1을 빼거나 2를 나눠 A와 같게 만들기

 

파이썬 코드 구현

A, B를 입력 받습니다.

A, B = map(int, input().split())

 

1. B의 마지막 자리가 1이면  10으로 나누고 나머지를 버려 B의 마지막 1의 자리를 없앱니다.

2. B가 2로 나눠지면 2로 나눠 B를 B/2로 만듭니다.

while A != B:
    cnt += 1
    if B % 10 == 1:
        B = B//10
    elif B % 2 == 0:
        B = B//2

 

만약 위의 연산중 어떤것도 작동하지 않으면 B는 A 가 될 수 없으므로 -1을 출력합니다.

(while문이 실행된 순간부터 A != B 라는것이 확실해집니다.)

else:
    cnt = -1
    break

혹은 B가 A보다 작다면 

B는 A 가 될 수 없으므로 -1을 출력합니다.

if B < A:
    cnt = -1
    break

print(cnt)

 

백준 16953 번 A → B 파이썬 최종 코드입니다.

import sys
input = sys.stdin.readline
A, B = map(int, input().split())
cnt = 1

while A != B:
    cnt += 1
    if B % 10 == 1:
        B = B//10
    elif B % 2 == 0:
        B = B//2
    else:
        cnt = -1
        break
    if B < A:
        cnt = -1
        break

print(cnt)

 

백준 16953 번 A → B 자세한 설명 및 파이썬 코드였습니다.

감사합니다.