[백준][파이썬]1463번 : 1로 만들기

개념 이해가 어려웠던 문제라 올려봤습니다..!
동적 계획법(Dynamic Programming), dp 에 관한 유형입니다.
기본적으로 '점화식' 을 구현해내는 방식인데, 다른 분들은 모르겠지만 저는 최근에 구현과 시뮬레이션 위주로 공부를 해서 그런지..너무 어려웠습니다..

n = int(input())
dp = [0 for _ in range(n+1)]
#여기서 dp[n] 는 n을 1로 만드는 최소한의 계산 횟수를 의미합니다.
for i in range(2, n+1):
    #1은 계산을 실행하지 않아도 1이기 때문에 1에서는 0이고, 2에서부터 시작합니다.
    #range를 사용할 경우 끝나는 값에 -1이 추가되기 때문에 n+1로 설정하였습니다.
    dp[i] = dp[i-1] + 1
    #일단 dp라는 리스트를 1부터 n까지의 수로 이루어진 리스트로 만들어줍니다.
    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])

주석으로 설명을 했지만 다시 저 스스로도 복기할 겸 개념을 정리하자면,
*리스트의 n번째 수가 for문 내의 if문으로 구현한 점화식대로 계산했을 때의 최소 횟수를 의미합니다.

*그렇기 때문에 각 i//2, i//3번째 '숫자'에 해당하는 최소 계산 횟수에 +1을 해주는 개념입니다.

*쉽게 설명하자면 최종적으로 얻어내는 1에서 주어지는 값까지 거슬러 올라가는 최소 횟수들을 저장해놓은 값이 dp라는 리스트 입니다.