SWEA 4869.종이 합치기
를 풀면서 DP를 처음 적용해보았다.
DP가 처음이라면 코드없는 프로그래밍
님의 영상을 추천한다.
https://www.youtube.com/watch?v=eJC2oetXaNk
이 글의 코드는 위 영상에서 피보나치로 설명하신 부분을 종이 합치기 문제에 적용한 것이다.
자기 자신을 호출
n을 더이상 쪼개지지 않을 때까지 쪼갠다.(하향식)
def paper_naive(n):
if n == 1:
return 1
elif n == 2:
return 3
else:
return paper_naive(n-1) + 2*paper_naive(n-2)
이전의 계산한 값을 저장함으로써 동일한 계산의 반복 수행 제거
arr = [0, 1, 3]
def paper_recur(n):
if n < len(arr):
return arr[n]
else:
paper = paper_recur(n-1) + 2*paper_recur(n-2)
arr.append(paper)
return paper
arr
: 계산값을 저장해두는 배열최대 재귀 깊이 초과
에러 발생def paper_dp(n):
if n == 1:
return 1
elif n == 2:
return 3
arr = [0, 1, 3]
for i in range(3, n+1):
paper = arr[i-1] + 2*arr(i-2)
arr.append(paper)
return arr[n]