✅ DP

문제

링크

1. 문제 접근 및 해결 로직

• 정의
  $dp[n][m]$ : 1~n 번째 인덱스까지의 배열에서 m개의 구간을 선택했을 때 구간합의 최대 값 메모이제이션
  $solve(n, m)$ : 1~n 번째 인덱스까지의 배열에서 m개의 구간을 선택했을 때 구간합의 최대 값 구하는 함수
• 구하는 답
• 초기값
• 점화식
  $dp[n][m]=max(solve(n-1, m),solve(i-2, m-1)+sum)$
  $sum$ : $n$에서 $i$까지 구간의 원소 합

• n번째 원소를 어느 구간에도 포함하지 않을 경우
  n을 제외한 범위를 다시 조정하여 구간합의 최대 값을 구한다.
  $dp[n][m]=solve(n-1, m)$
• n번째 원소를 한구간의 원소로 포함하는 경우
  $dp[n][m]=solve(i-2, m-1)+sum$
  (구간끼리는 인접할 수 없으므로 $i-1$이 아니라 $i-2$가 들어감, n번째 원소가 포함한 구간을 하나 사용했으므로 $m-1$개의 구간을 찾음)
• n번째 원소를 하나의 원소로 갖는 구간의 경우는 생각하지 않는다. 왜냐하면

https://velog.io/@keybomb/BOJ-2228-%EA%B5%AC%EA%B0%84-%EB%82%98%EB%88%84%EA%B8%B0-C

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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