[백준 알고리즘] 1463번: 1로 만들기 (Python / 파이썬)

문제 링크

1463번: 1로 만들기

 

문제 접근

DP 테이블을 이용한다.

현재 자신(숫자)를 만들기 위해 필요했던 연산의 개수를 저장한다.

각 수 연산을 다 해주고, 이 연산을 거친 결과를 서로 비교해서 가장 최솟값을 DP 테이블에 순차적으로 저장한다.

 

정답 코드

import sys

X = int(sys.stdin.readline())

dp = [0] * (X + 1)

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

print(dp[X])