파이썬 알고리즘 192번 | [백준 1463번] 1로 만들기 - DP

192. 1로 만들기

1) 어떤 전략(알고리즘)으로 해결?

• 전의 결과를 다음 결과에 이용하는 DP

2) 코딩 설명

<내 풀이>

import sys

n= int(sys.stdin.readline().rstrip())
cnt=0

# 전의 결과를 다음 결과에 이용하는 DP 문제입니다. 
dp = [0 for _ in range(n+1)]

for i in range(2,n+1) : #1운 항상 0 (바로 1이니깐요)
    cand = dp[i-1]
    if i%2 == 0 :
        cand = min(cand, dp[i//2])
    if i%3 == 0 :
        cand = min(cand, dp[i//3])
    dp[i]=cand+1

print(dp[n])

<반성 점>

• 작은 것이 큰 것으로 발전해나가는 과정을 생각하고 떠올리자

<배운 점>

• dp 의 개념 반복