728x90
subproblem 중복, 반복연산 많음 -> DP
풀이1 (Bottom-up)
n = int(input())
dp = [0] * (n+1)
for i in range(2, 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(i, ": ", dp[i])
if n <= 1:
i = 0
print(dp[i])
풀이2 (Top-Down) - Recursion Error
def min_operations(n, dp):
if n <= 1:
return 0
if dp[n] > 0: # 이미 계산된 값이 있다면 그 값을 반환
return dp[n]
dp[n] = min_operations(n-1, dp) + 1
if n % 3 == 0:
dp[n] = min(dp[n], min_operations(n//3, dp) + 1)
if n % 2 == 0:
dp[n] = min(dp[n], min_operations(n//2, dp) + 1)
return dp[n]
n = int(input())
dp = [0] * (n+1)
print(min_operations(n, dp))Top down으로도 구현할 수 있지만 Recursion Error가 발생했다.
Recursion Error?
재귀와 관련된 에러. 주로 Python이 정한 최대 재귀 깊이보다 더 깊어질 때.
해결방법 2가지
1. 재귀함수 사용하지 않는 것
- DFS -> BFS
- DP에서는 Top-down -> Bottom-up
2. sys.setrecursionlimit()으로 최대 재귀 깊이 변경
import sys
sys.setrecursionlimit(10**6)
와 같이 변경할 수 있으나.. 결국 채점 서버가 감당할 수 있는 정도여야 하므로 비추
https://help.acmicpc.net/judge/rte/RecursionError
TypeError: list indices must be integers or slices, not float
인덱스 다룰 때 -> / 가 아닌 // 로 몫 구하기
/를 한다면 다음과 같은 에러가 난다.
dp[i] = min(dp[i/2]+1, dp[i])
TypeError: list indices must be integers or slices, not float
728x90
