1로 만들기 - 동적 프로그래밍 - 2021/05/03

1로 만들기

n이 주어지고 1씩 빼는것과 2,3,...으로 나누는것이 가능할 때, n을 1로만드는 최소 횟수를 구하는 문제

 

이 문제도 DP를 이용하여 풀 수 있다.

 

x=int(input())

d=[0]*(x+1)
for i in range(2,x+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[x])

먼저 1을 빼는 값을 d에 저장하고 나눌수 있을 때, 나눈 d의 값에 1을 더한값과 비교하여 더 작은값을 저장한다.