[Silver III] 정수 a를 k로 만들기 - 25418 (python)

문제 링크

 

분류

너비 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색

 

문제 설명

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

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

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

입력

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

출력

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

 

 

코드

 

1.  dp로 풀기

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

for num in range(a, k):
    if num+1 <= k and dp[num+1] == 0:
        dp[num+1] = dp[num]+1
    if num*2 <= k and dp[num*2] == 0:
        dp[num*2] = dp[num]+1

print(dp[k])

 

 

 

2.  a부터 늘려가는 것이 아닌 k를 줄여가며 a가 되는 횟수 확인

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

ans = 0
while a!=k:
    if k%2 == 0 and k//2 >= a:	# k가 짝수이면서 나누었을시 a보다 같거나 커야한다.
        k //= 2
    else:
        k -= 1

    ans += 1

print(ans)