[이것이 코딩 테스트다] 1로 만들기 - 다이나믹 프로그래밍

백준 1로 만들기와 같은 유형의 문제다.

---

X에서 1로 만들기 방법이다.

 

X에서 1로 한 번 순회한다.

현재 위치 i (1<i<=X)에서 연산가능한 모든 숫자에 최소 연산 횟수를 기록한다.i가 1이 될 때까지 위 과정을 반복한다.

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

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

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

---

1에서 X 만들기 방법도 이 문제를 해결할 수 있다.

풀이과정이다. 필요한 분께서 보시고 이해하시는 데에 도움이 되면 좋겠다.

 

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을 한 값으로 결정난다.

• 유의할 점⛔
• 파이썬의 '//' 연산은 몫 연산이다. 무지성 min(dp[i-1], dp[i//2], dp[i//3], dp[i//5])을 해버리면, 원치 않은 값을 얻을 수 있다.

# 1에서 X 만들기
X = int(input())

dp = [10**8] * (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])
    if i%5 == 0:
        dp[i] = min(dp[i//5] + 1, dp[i])

print(dp[1:])
print(dp[X])