1로 만들기

 

문제

X가 주어질 때, 5, 3, 2로 나누거나 1을 빼서 결과적으로 1을 만들 때, 

가장 최소의 연산의 수로 1을 만들어라

 

 

유형 파악 및 구현

전형적인 DP문제이다.

예전에 구한 값이 지금 현재 구하고자 하는 값에 영향을 준다

 

예를 들어, 26을 1로 만든다고 생각을 해보자

 

- 26은 5나 3으로는 나누어지지 않는다.

- 26은 2로 나누거나 1을 뺄 수 있다.

 

이 때,

2로 나누는 경우 - 13에서 1을 만들기 위한 최소한의 연산의 수 + 1

1을 빼는 경우 - 25에서 1을 만들기 위한 최소한의 연산의 수 + 1

 

즉, 13 또는 25를 1로 만들기 위해 사용되는 연산의 수 + 1을 하고 둘 중 작은 값이 정답이 된다.

 

x 를 1로 만드는 횟수

1 : 0

2 : min(2//2를 1로 만드는 횟수+1 , 2-1을 1로 만드는 횟수 + 1 )

....

...

8 : min( 8//2, 즉 4를 1로 만들기 위한 횟수 + 1, 8-1 즉 7을 1로 만들기 위한 연산의 횟수 + 1)

 

 

코드

n = int(input())
INF = 1e9
check = [INF]*(n+1)
check[1] = 0
check[2] = 1
for i in range(3, n+1):
    if i % 2 == 0:
        check[i] = min(check[i], check[i//2]+1)
    if i % 3 == 0:
        check[i] = min(check[i], check[i//3]+1)
    if i % 5 == 0:
        check[i] = min(check[i], check[i//5]+1)
    check[i] = min(check[i], check[i-1]+1)
print(check[n])