1463번 1로 만들기

def counter(n):
    dp = [0] * (n + 1)

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + 1

        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)

        # 3으로 나누어 떨어지는 경우
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)

    return dp[n]

n = int(input())
print(counter(n))

숫자 i를 1로 만들 수 있는 최소 계산 횟수를 dp[i] 라고 정의하면,

기본적으로 +1연산에 의해 1개씩 증가하고,

2로 나누어떨어지는 i의 경우 2분의 1 위치의 dp에 1을 더한 방법과 이전 수에 1을 더한 방법 중 최소 횟수를 저장한다.

3로 나누어떨어지는 i의 경우 3분의 1 위치의 dp에 1을 더한 방법과 이전 수에 1을 더한 방법 중 최소 횟수를 저장한다.

[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 1, 1, 2, 0, 0, 0, 0, 0, 0]

[0, 0, 1, 1, 2, 3, 0, 0, 0, 0, 0]

[0, 0, 1, 1, 2, 3, 2, 0, 0, 0, 0]

[0, 0, 1, 1, 2, 3, 2, 3, 0, 0, 0]

[0, 0, 1, 1, 2, 3, 2, 3, 3, 0, 0]

[0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 0]

[0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3]