[백준] 1463 '1로 만들기' 파이썬(python)

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

1463번: 1로 만들기

n = int(input())
dp = [0] * (n+1)	# DP 테이블 만들기

for i in range(2, n+1) :	# 전의 결과를 다음 결과에 이용하게 되는 점화식 활용 DP 문제이다.
    dp[i] = dp[i-1] + 1		# 나누어 떨어지지 않을 경우에는 무조건 1을 빼야하기 때문에 횟수 +1을 해준다.
    
    if i % 2 == 0 : 	# 나누어 떨어질 경우에는 1을 빼는 것보다 나누어 떨어지는 것이 더 효율적이기 때문에 두개 중에 비교
        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])

Point

• 전의 결과를 다음 결과에 이용하는 점화식을 활용한 DP 문제.
• 9의 경우에는 9 - 3 - 1 이 되며, 3의 경우에는 3 - 1 이 된다.
• 결국 9를 구하려면 3을 구하게 되어야 하며 이는 작은 것들을 합쳐 큰 문제를 해결해 나가는 것이라 볼 수 있다.