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

 

📌 문제 탐색하기

• 정수 A를 정수 K로 만들기 위해 두 가지 연산만 사용 가능
  • 정수 A에 1 더하기
  • 정수 B에 2 곱하기
• 위 두가지 연산을 통해 주어진 A를 K로 만들기 위한 최소 연산 횟수 구하기
• 범위 : 1 ≤ A < K ≤ 1,000,000

처음 보자마자 떠오른 방법은 동적 계획법(DP)로 풀이하는 방법이다. A가 A부터 K가 되기 전까지 두가지 연산을 통해 각 수를 만들 수 있는 최소 연산 횟수를 저장해놓고, 그 저장된 값을 나중에 다시 활용하는 방식이다.

 

점화식은 아래와 같이 세울 수 있다.

• n이 홀수일 경우, dp[n] = dp[n-1]+1
• n이 짝수일 경우, dp[n] = min(dp[n-1], dp[n//2])+1

A에서 K까지 순차적으로 값을 갱신해야하기 때문에 시간복잡도는 O(K-A)가 된다. 

 

---

📌 코드 설계하기

1. A와 K를 입력받는다.
2. dp 리스트를 생성하고, 리스트의 모든 원소의 값을 K로 초기화 한다.
3. i가 A+1부터 K일때까지, 점화식을 이용하여 dp[i]값을 구한다.
4. dp[K]를 출력한다.

dp 리스트의 원소 값을 K로 초기화 한 이유

K는 이 문제에서 가능한 최대 연산보다 무조건 큰 값이다. A에서 K로 가기 위해선 최소한의 연산이 필요하기 때문에 초기값으로 K를 설정하면, 추후에 실제 계산한 연산 횟수와 비교하는 과정에서 무조건 갱신되게 된다. 즉, dp[n] = K라면, 아직 계산되지 않았다는 의미를 갖게 된다. 

 

---

📌 정답 코드

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

dp = [K]*(K+1) # dp[n] = A를 n으로 만들기 위해 필요한 최소 연산 횟수
dp[A] = 0

for i in range(A+1, K+1):
  dp[i] = dp[i-1] + 1
  if i%2 == 0:
    dp[i] = min(dp[i-1], dp[i//2]) + 1

print(dp[K])