코드

N = int(input())

# DP 테이블 생성
d = [0] * (N+1)

for i in range(2, N+1):
    d[i] = d[i-1] + 1
    
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
        
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)

print(d[N])

문제 해설

동적 프로그래밍 참고

대표적인 동적 프로그래밍 문제. 동적 프로그래밍 문제에서 가장 핵심은 역시 점화식을 만드는 능력이다.

(위 링크에 이와 유사한 문제가 있으므로 참고바랍니다!)

댓글남기기

참고