[백준 25418] 정수 a를 k로 만들기 python

문제

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

 

풀이

백준 BFS 연습 문제인 숨바꼭질과 비슷해 보이지만 해당 문제는 단순히 값이 증가만 한다. 값 증가만 이루어지므로 반복문을 통해 a부터 k까지 단순하게 돌려주면 정답을 구할 수 있다.

최솟값을 찾는 문제이므로 초기값은 큰 값으로 설정해주었다.

1. i가 2의 배수라면(i%2가0이라면) 2로 나눌 수 있다. -> i/2 에 2를 곱해서 i를 만들 수 있다.
2. i에서 1을 빼서 i-1을 만들 수 있다.  -> i-1에 1을 더해서 i를 만들 수 있다.

위 규칙을 이용해 코드를 짜면 된다.

from sys import stdin
input=stdin.readline

a,k=map(int,input().split())
dp=[1e9]*(k+1)

dp[a]=0
for i in range(a+1,k+1):
    dp[i]=min(dp[i-1],dp[i//2] if i%2==0 else 1e9)+1

print(dp[k])