백준 / 1463번 / 1로 만들기 / DP / python 파이썬

 

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

 

 

코드 

import sys
n = int(sys.stdin.readline())

d = [0] * (n + 1)

for i in range(2, n + 1):
    d[i] = d[i-1] + 1

    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1)
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2] + 1)
print(d[n])

 

DP를 이용해 모든 숫자에 대해 /3, /2, -1을 하는 함수를 호출할 필요없이 이전에 계산한 정보들을 사용하여 푸는 것이 핵심이다. DP 테이블에 해당 숫자를 만드는데 필요한 최소 연산 횟수를 갱신해가며 저장하면 d[n]에는 n을 1로 만드는 최소 연산 횟수를 구할 수 있다.

 

 

알게된 것