import sys
sys.setrecursionlimit(10**6)
n = int(input())
dp = [0] * (n + 1)
def get_dp(n):
if n == 1:
return 0
elif dp[n] != 0:
return dp[n]
else:
a, b = 1e9, 1e9
if n % 3 == 0:
a = get_dp(n // 3) + 1
if n % 2 == 0:
b = get_dp(n // 2) + 1
c = get_dp(n - 1) + 1
dp[n] = min(a, b, c)
return dp[n]
res = get_dp(n)
print(res)
반복문으로 다시 풀면 다음과 같다.
n = int(input())
dp = [0] * 1000001
for i in range(2, n + 1):
a, b = 1e9, 1e9
if i % 2 == 0:
a = dp[i // 2] + 1
if i % 3 == 0:
b = dp[i // 3] + 1
c = dp[i - 1] + 1
dp[i] = min(a, b, c)
print(dp[n])
다른 사람 풀이
재귀를 사용하려면 $DP[N-1]$로 재귀 함수가 실행되지 않아야 한다.
아래 코드의 경우 $DP[N//3]$과 $DP[N//2]$과정에 나머지 값을 더하여 해결했다.
좋은 아이디어!
import sys
read = sys.stdin.readline
N = int(read())
cache = {1: 0, 2: 1}
def dp(n):
if n in cache:
return cache[n]
# 핵심 코드
cnt = 1 + min(dp(n//3) + n%3, dp(n//2) + n%2)
cache[n] = cnt
return cnt
print(dp(N))