[BOJ] 16953. A → B

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

16953번: A → B

 

 

1. 해결방법

"""
1. 아이디어
- 그리디 알고리즘
    - Top-down 방식
    - x2 또는 +1 두 가지 경우의 수가 존재
    - 먼저 B가 2의 배수인지 확인 -> B // 2
    - 2로 나누다가 일의 자리 숫자가 1인 경우 (if문) 일의 자리 삭제 -> B // 10
- BFS
    - Bottom-up 방식
    - A와 횟수 answer(초기값 1)을 큐에 넣는다.
    - 여기서 두 가지 방향이 있는데,
        - 1. A에서 2를 곱하고 answer + 1을 한다.
        - 2. A에서 10을 곱하고 +1을 한 다음, answer + 1을 한다.
    - while문 안의 큐에 들어있는 now 변수가 B와 같아지면 print(count)
    - 만약 B와 같지 않다면 print(-1)
2. 시간복잡도
- O(2N) == O(N)
"""

 

 

2. 정답코드

# 그리디 알고리즘
import sys
input = sys.stdin.readline

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

answer = 1

while True:
    # 종료 지점
    if A == B:
        print(answer)
        break
    elif ((B % 2 != 0) and (B % 10 != 1)) or (A > B) :
        print(-1)
        break

    # 2로 나누어 떨어질 때,
    if B % 2 == 0:
        B //= 2
        answer += 1
        continue

    # 2로 나누어 떨어지지 않을 때,
    elif B % 2 == 1:
        B //= 10
        answer += 1
        continue


# BFS
from collections import deque
import sys
input = sys.stdin.readline

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

answer = 1

 

# BFS
from collections import deque
import sys
input = sys.stdin.readline

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

answer = 1


def bfs():
    q = deque()
    q.append((A, 1))

    while q:
        now, count = q.popleft()

        # 종료 지점
        if now == B:
            return print(count)


        if now * 2 <= B:
            q.append((now * 2, count + 1))

        if now * 10 + 1 <= B:
            q.append((now * 10 + 1, count + 1))

    return print(-1)

bfs()

로직 자체가 크게 어렵지 않은 문제였다. 푸는 방법은 그리디와 BFS가 있는데 이 두가지는 접근하는 방법이 약간 다르다. 그리디는 B에서 A를 만드는 것이고, BFS는 A에서 B를 만드는 경우를 나타낸 것이다. 이 부분을 생각했다면 2를 곱하는 로직은 어렵지 않지만, 1을 일의 자리 숫자에 끼워 넣는 것이 문제였을 건데그 부분은 파이썬 연산자 '//' 와 '%'를 잘 이용하면 쉽게 풀 수 있는 문제다.