[BOJ#25418] 정수 a를 k로 만들기

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

25418번: 정수 a를 k로 만들기

1 초

512 MB

2451

1524

1262

63.802%

문제

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

입력

첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다.

제한

1 ≤ A < K ≤ 1,000,000

---

제출 코드

from collections import deque

def calc(start, cnt):
    global ans
    
    q = deque()
    q.append([start, cnt])

    while q:
        start, cnt = q.popleft()
        if start == K:
            ans = cnt
            break
        if start > K:
            continue
        
        if visited[start] == 1:
            continue
        visited[start] = 1
        q.append([start+1, cnt+1])
        q.append([start*2, cnt+1])


A, K = map(int, input().split())
visited = [0] * 1000001
ans = 1e9
calc(A, 0)
print(ans)

 

최초 값을 들고 bfs 로 들어가서 이미 방문한 곳을 체크하면서 최소연산을 찾아갔다.

원래 visited 를 안쓰고 재귀를 활용했었는데 3번째 테스트케이스에서 recursion 에러가 떠서 bfs로 노선을 바꿨다.

 

bfs에서 최초 값에 연산한 값들을 넣어주면서 방문을 체크하기 때문에 한번 들른 곳

(1번 연산으로 도착한 연산수와, 2번 연산으로 도착한 연산 수가 같기 때문에 방문표시로 배제 가능)

은 다시 들르지 않고 지나가서 값이 잘 나온것 같다.