[S3] 백준 1463 - 1로 만들기(Python)

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

 

---

풀이👀

1부터 X까지 반복문으로 1회 순환한다.
i (1<i<=X)에 대해서 dp[i]라 할 때, dp[i]는 1에서 출발하여 주어진 조건을 만족하며 i를 만들기 위해 필요한 연산 최소 횟수이다.
그러면
dp[i]는 (dp[i-1], dp[i//2], dp[i//3], dp[i//5]) 중에서 최솟값을 찾은 다음, +1을 한 값으로 결정난다.

---

코드💻

# 1로 만들기
X = int(input())

dp = [10**7] * (X+1)
dp[1] = 0

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