[백준] 정수 a를 k로 만들기 (25418번)

난이도 : Silver3
Link : https://www.acmicpc.net/problem/25418
Tag : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색
풀이일자 : 2024년 9월 25일

📌 문제 탐색하기

A : 주어진 양의 정수
K : 만들 정수

연산 1번 : A + 1
연산 2번 : A * 2
본 문제는 A에서 1번 연산방법과 2번 연산방법을 이용하여 최소 연산으로 K를 만들어내는 문제이다.

가능한 시간복잡도

1 ≤ A < K ≤ 1,000,000 이므로
최대한 적은 연산의 모든 경우의 수를 탐색하려고 했을때 연산 2번을 통해 A와 K의 격차를 크게 줄일 수 있으므로 시간 복잡도 상 문제는 없을 것으로 보인다.

📌 문제 접근 방법

이 문제를 보는 순간 접근 방법은 두가지로 떠올랐다.
첫번째 방법은 DP 방법으로 연산 1번 2번의 경우들을 저장하면서 A가 K랑 같아지는 경우를 찾는경우이다.
두번째 방법은 BFS 방법으로 방문 노드를 확인하고, 방문한 적이 없다면 연산을 진행하여 만들 수 있는 정수들을 찾고 K와 같아졌을 때 값을 찾아내는 것이다.

첫번째 방법으로 본 문제를 풀려고 접근했으나, 각 연산 방법을 정할때마다 2가지 경우로 나눠지는 것을 생각했을 때 배열의 크기가 너무 커질 것이라 생각이들어 두번째 방법으로 문제를 접근하였다.

📌 코드 설계하기

1. a, k를 입력받는다.
2. queue에 a값과 연산 횟수를 deque로 추가한다
3. visited 배열에 a 값을 집합형식으로 저장한다
   • 배열 형식으로 했을 때 찾는 시간복잡도 보다 집합 형식의 시간복잡도가 적게 걸리기 때문이다.
4. queue값이 있을때 까지 BFS 탐색을 진행한다.
   • now에 현재값을 answer에 연산 횟수를 저장한다.
   • 만약 now값이 k와 같을 경우 반복문을 종료하고 answer값을 출력한다.
   • 만약 now+1값이 visited에 없고 k보다 작거나 같으면 queue에 now값과 연산횟수 answer를 업데이트 한다.
   • 만약 now*2값이 visited에 없고 k보다 작거나 같으면 queue에 now값과 연산횟수 answer를 업데이트 한다.

📌 시도 회차 수정 사항

📌 정답 코드

from collections import deque

a,k = map(int,input().split())

queue = deque([(a,0)]) #a값, 연산횟수
visited = set([a])
answer = 0
while queue:
    now, answer = queue.popleft()

    if now == k:
        break
    if (now + 1) <= k and (now + 1) not in visited:
        visited.add(now + 1)
        queue.append((now+1, answer+1))
    if (now * 2) <= k and (now * 2) not in visited:
        visited.add(now * 2)
        queue.append((now*2 , answer + 1))


print(answer)