[DP] 1로 만들기

1. 문제 설명

- 주어진 수를 1로 만들기 위해 수행해야 하는 연산의 횟수를 구하는 문제

- 2, 3, 5를 나누는 연산이 존재

2. 코드

n = int(input())
df = [0]*(n+1)

for i in range(2, n+1):
    df[i] = df[i-1]+1
    if i%2==0:
        df[i] = min(df[i], df[i//2]+1)
    elif i%3==0:
        df[i] = min(df[i], df[i//3]+1)
    elif i%5==0:
        df[i] = min(df[i], df[i//5]+1)
print(df[n])

"""
6
>> 2
"""

3. 코멘트

- 코드는 간단했으나 횟수 추가 부분을 이해하는데 시간이 좀 걸렸었다.

- 문제 풀이 방식이 DP였다는 것을 생각해서 이해를 했던 것 같다.