✅ DP

문제

링크

1. 문제 접근 및 해결 로직

n번째 곡의 볼륨이 하나로 정해지지 않고 가능한 모든 경우를 고려해야한다.

• 정의
  $dp[n][v]=true$ $orfalse$ : n번째 곡을 볼륨 v으로 연주 할 수 있는지 없는지
• 구하는 답
  $v(->dp[n][v]!=-1,-1<v<=M)$
• 초기값
  $dp[1][S]=true$
• 점화식
  $if (j + arr[n] <= M),dp[n][j + arr[n]] = true$
  $if (j - val >= 0),dp[n][j - arr[n]] = true$
  $j$는 $dp[n-1][v]==true$ 를 만족하는 $v$

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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