백준 16953 A → B 문제 파이썬 풀이

🔷 백준 16953 A → B 문제 파이썬 풀이

✅ 문제

🔷 문제

정수 \( A \)와 \( B \)가 주어졌을 때, 아래의 두 가지 연산만을 사용하여 \( A \)를 \( B \)로 만들 수 있는지 확인하고, 만들 수 있다면 최소 연산 횟수를 출력합니다. 만들 수 없다면 -1을 출력합니다.

허용된 연산은 다음과 같습니다.

• 현재 수에 \( 2 \)를 곱합니다.
• 현재 수의 오른쪽 끝에 \( 1 \)을 붙입니다. (예: 23 → 231)

🔷 테스트케이스

입력

2 162
    

출력

5
    

입력

4 42
    

출력

-1
    

🔷 문제설명

두 정수 \( A \)와 \( B \)가 있습니다. 이때 \( A \)에서 출발하여 \( B \)에 도달해야 합니다. 단, 한 번에 \( A \)를 두 배하거나, 오른쪽에 1을 붙이는 두 가지 방법밖에 쓸 수 없습니다.

예를 들어 \( A = 2 \), \( B = 162 \)인 경우를 살펴보겠습니다.

• 2 → 4 (두 배)
• 4 → 8 (두 배)
• 8 → 81 (오른쪽에 1 붙이기)
• 81 → 162 (두 배)

이렇게 하면 총 5번 만에 \( A \)에서 \( B \)로 갈 수 있습니다. 따라서 출력값은 5입니다. 반대로 \( A = 4 \), \( B = 42 \)라면, 아무리 두 배하고 1을 붙여도 42를 만들 수 없습니다. 이때는 -1을 출력합니다.

✅ 문제 아이디어

이 문제는 역방향 탐색이 더 효율적입니다. \( B \)에서 \( A \)로 거꾸로 내려오며, 두 가지 연산의 역연산을 수행해 보는 것입니다.

🔷 핵심 아이디어

1. 역순으로 나누어서 원래 값이 나오는지 확인합니다.
• 예를 들어 \( B = 162 \)라면 \( A = 2 \)로 만들기 위해 \( 162 → 81 → 8 → 4 → 2 \)로 내려갑니다.
• 이때 역연산은 오직 두 가지입니다.
2. \( B \)가 짝수이면 \( 2 \)로 나눕니다.
• \( 162 \)는 짝수라서 \( 162/2 = 81 \)이 됩니다.
3. \( B \)의 마지막 자리가 \( 1 \)이면 \( 10 \)으로 나눕니다.
• \( 81 \)의 경우 끝자리가 \( 1 \)이라서 \( 81/10 = 8 \)이 됩니다.
4. 이렇게 해서 값이 \( A \)에 도달하면 연산 횟수를 출력합니다. 도달하지 못하면 \(-1\)을 출력합니다.

✅ 전체 코드

N, M = map(int, input().split())
cnt=1
while(M>N):
    if M%2==0:
        M=M//2
    elif M%10==1:
        M=M//10
    else:
        break
    cnt+=1

if (N==M):
    print(cnt)
else:
    print(-1)
    

✅ 개별 코드

🔷 입력 받기

N, M = map(int, input().split())
    

두 개의 정수를 입력받습니다. \( N \)은 시작 수, \( M \)은 목표 수입니다.

🔷 반복문으로 역연산 수행

while(M>N):
    

\( M \)이 \( N \)보다 큰 동안 반복합니다. \( M \)이 \( N \)보다 작아지면 목표를 달성할 수 없기 때문입니다.

🔷 역연산 조건 1: 짝수

if M%2==0:
    M=M//2
    

\( M \)이 짝수일 때 \( 2 \)로 나눕니다. 정방향에서 \( \times 2 \) 한 것을 되돌리는 연산입니다.

🔷 역연산 조건 2: 끝자리가 1

elif M%10==1:
    M=M//10
    

\( M \)의 끝자리가 \( 1 \)이라면 오른쪽 끝의 \( 1 \)을 제거하고 \( /10 \) 합니다. 정방향에서 \( x \to x*10+1 \) 한 것을 되돌립니다.

🔷 그 외의 경우

else:
    break
    

짝수도 아니고 끝자리가 1도 아니라면 더 이상 진행이 불가능합니다. 반복을 종료합니다.

🔷 최종 판정

if (N==M):
    print(cnt)
else:
    print(-1)
    

반복을 끝낸 후 \( N \)과 \( M \)이 같다면 성공입니다. 연산 횟수를 출력합니다. 같지 않다면 목표에 도달할 수 없는 경우이므로 \(-1\)을 출력합니다.

✅ 결론

• 두 수가 주어졌을 때 \( A \to B \)로 가는 문제는 역방향으로 푸는 것이 더 효율적입니다.
• 짝수이면 \( 2 \)로 나누고, 끝자리가 \( 1 \)이면 \( /10 \)을 합니다.
• 그 외의 경우에는 더 이상 진행이 불가능하니 \(-1\)을 출력합니다.
• 시간 복잡도가 매우 낮아 빠르게 풀이할 수 있습니다.

✅ 핵심 요약

• ✅ \( A \to B \)를 역방향으로 생각하여 빠르게 해결합니다.
• ✅ 짝수와 끝자리가 1인 경우만 처리합니다.
• ✅ 불가능한 경우를 정확히 판별해야 합니다.
• ✅ 단순한 구현이지만 직관적인 로직입니다.