[Python] 1463. 1로 만들기

n = int(input())

dp = [0 for _ in range(n+1)]

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

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

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

print(dp[n])

dp 리스트 안의 i 자리에는 숫자 i를 1로 만들기 위한 주어진 연산을 사용하는 횟수의 최솟값이 담기게 된다.
따라서 2부터 시작하여 (1은 연산할 필요가 없으므로 0) n까지 저장하는 dp를 이용하여 문제를 풀어야 한다. 

1. >dp[i]에 이전의 숫자(i-1)에서 구한 연산 사용 횟수 +1을 저장한다. 
   • 예) i = 10이라면 dp[9] = 2 이므로, dp[10] = 3 이 된다. 
2. i가 3으로 나누어떨어진다면, 1번에서 저장한 이전 수에서의 연산 사용 횟수 +1 한 것과 i를 3으로 나눈 수에서의 연산 사용 횟수 +1 중 작은 수를 dp[i]에 저장한다.
   • 예) i = 9라면, dp[i] = dp[9-1] = 3 과 dp[i//3]+1 = dp[3]+1 = 2 중 작은 숫자인 2를 dp[9]에 저장한다. 
3. i가 2로 나누어떨어진다면, 1번에서 저장한 이전 수에서의 연산 사용 횟수 +1 한 것과 i를 2으로 나눈 수에서의 연산 사용 횟수+1 중 작은 수를 dp[i]에 저장한다.
   • 예) i = 10이라면, dp[i] = 3 (위의 1번 참고) 과, dp[i//2]+1 = dp[5]+1 = 2 + 1 = 3 를 비교하는데, 연산 횟수가 같으므로 dp[10]에 3을 저장한다. 

따라서 점화식은 dp(n) = min(dp(n-1)+1, dp(n//3)+1, dp(n//2)+1)이 된다.