✅ DP

문제

링크

1. 문제 접근 및 해결 로직

구하고자 하는 값이 가능한 수식의 수이므로 dp에는 n번째까지 가능한 수식의 수를 저장하면서 진행해야 한다.

n번째 수를 수식에 사용할 수 있는지 없는지는 n-1에서의 값에 n번째 수를 더하거나 뺐을때 0 이상 20 이하인지 아닌지에 따라 결정된다.

• 정의
• 구하는 답
  $dp[N-1][arr[N]]$
• 초기값
  $dp[1][arr[1]]=1$
• 점화식
  $if(j+arr[n]<=20) dp[n][j+arr[n]]+=dp[n-1][j]$
  $if(j-arr[n]>=0) dp[n][j-arr[n]]+=dp[n-1][j]$
  $j$ 는 $dp[n-1][j]>0$을 만족하는(바로 전 수까지 사용했었는지) j

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항