2021.2.10 [백준] 1로 만들기

다이나믹 프로그래밍 알고리즘

 

 

Q

 

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

A

 

다이나믹 프로그래밍을 이용하여 풀었다. 주의할 점은 DP 테이블의 크기를 입력받는 n으로 설정하지 말고 n의 최대 크기를 보고 정수로 설정하자.

 

코드

import sys

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

 

d = [0] * (10**6 + 1) #DP 테이블 초기화
d[1] = 0
d[2] = 1
d[3] = 1

for i in range(4, n + 1):
    d[i] = d[i-1] + 1 #-1을 뺀 경우
    if i % 2 == 0:
        d[i] = min(d[i//2] + 1, d[i]) #2로 나눈 행위 자체가 1번의 행위이므로 +1 해주기
    if i % 3 == 0:
        d[i] = min(d[i//3] + 1, d[i]) #3으로 나눈 행위 자체가 1번의 행위이므로 +1 해주기
    
print(d[n])