문제

https://www.acmicpc.net/problem/1463

나의 코드 (답안 참고)

"""
1. 아이디어

2. 시간복잡도
O(N-2)정도? n이 2이상일때
"""

from sys import stdin
input = stdin.readline

n = int(input())
dp = [0] * (n+1)
# dp[i] = i를 1로 만들 수 있는 연산의 최솟값

for i in range(2, n+1):
    dp[i] = dp[i-1] + 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])

    

느낀점

주어진 연산을 반복하여 X를 1로 만들 수 있는 최솟값을 출력하면 된다.

각 연산에 대해 좀 더 깊게 알아보자

1. X가 3으로 나누어 떨어진다면? dp[n] = dp[n/3] + 1
2. X가 2로 나누어 떨어진다면? dp[n] = dp[n/2] + 1
3. 1을 뺄 경우? dp[n] = dp[n-1] + 1

잘 이해가 안된다면, X에 숫자를 직접 넣어서 생각해보자.
X를 6이라고 가정하자.

1. 6은 3으로 나누어 떨어지므로 dp[6] = dp[2] + 1 (2에서 3을 곱하면 6이된다. 즉 dp[2]에서 3을 곱하는 연산을 한 번 더 하면 6을 만들 수 있다.)

2. 6은 2으로 나누어 떨어지므로 dp[6] = dp[3] + 1 (3에서 2을 곱하면 6이된다. 즉 dp[3]에서 2를 곱하는 연산을 한 번 더 하면 6을 만들 수 있다.)

3. 6에서 1을 빼면 5가 되므로 dp[6] = dp[5] + 1(5에서 1을 더하면 6이 된다. 즉 dp[5]에서 1을 더하는 연산을 한 번 더 하면 6을 만들 수 있다.)

이 3가지 방법 중에서, 가장 연산 횟수가 적은 경우의 수를 찾아야한다.
따라서 구하고자하는 점화식은 다음과 같다.

dp[n] = min(dp[n/3] +1, dp[n/2] + 1, dp[n-1] + 1) = min(dp[n/3], dp[n/2], dp[n-1]) + 1