백준_1463_1로 만들기(DP)

n = int(input())

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

    print(dp[n])

1부터 n까지 차례대로 구할 수 있는 최소한의 횟수를 구해나가는 방식이다.
우선 숫자 n은 n-1로 부터 +1 하는 계산으로 구할 수 있다. 그 다음 3으로 나누어 떨어지는 숫자의 경우와 2로 나누어 떨어지는 숫자의 경우 각각 dp[n//3], dp[n//2]으로 부터 그 값 들의 횟 수들을 비교하는 방법으로 구할수 있다.