1463번 : 1로 만들기

문제

파이썬

n = int(input())

dp = [0] * (n+1)

for i in range(2, n+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[n])

풀이

• 단순히 큰 수로 나누어떨어지는지 확인하고 -1 씩하는 그리디의 방식으로 접근하기에는 10일때 10 -> 5 -> 4 -> 2 -> 1 의 4번의 수행보다 10 -> 9 -> 3 -> 1 로 가는 방식이 빠름
• 나누어 떨어지지 않을경우 -1 을 진행하는건 똑같으니 기본적으로 dp[n+1] = dp[n] + 1 의 형태를 가짐
• 2,3 으로 나누어 떨어질때는 min 연산을 통해 어느 값이 더 최솟값인지를 확인