dynamic programming11 [Python]16194. 카드 구매하기 2 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 점화식 dp[i] 를 구하기 위해선 p[1] + dp[i-1] p[2] + dp[i-2] p[3] + dp[i-3] ... p[j] + dp[i-j] 까지 구해야 하며, 주어진 문제조건에 따라 이 중 에서 가장 작은 값이 dp[i]가 된다. 다시 말해, dp[i] = min(p[1] + dp[i-1], p[2] + dp[i-2], p[3] + dp[i-3], ... , p[j] + dp[i-j]) 여.. 2019. 4. 3. [Python]1463. 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #Top-down 방식 : 재귀호출 이용 import sys sys.setrecursionlimit(10000000) #재귀 한도를 늘려준다. RecursionError 방지 def dp(x): if x == 1: m[x] = 0 return m[x] if m[x] > 0: return m[x] m[x] = dp(x-1)+1 # 빼기 1 연산, 메모이제이션 + 초기화 기능 if .. 2019. 4. 2. 이전 1 2 다음 728x90 반응형