✅ DP

문제

링크

1. 문제 접근 및 해결 로직

• 정의
  $DP[pos][cnt][time] = value,(pos=1or2,0<cnt<=W,0<time<T)$
  1.pos : 현재 위치 (1번 나무 or 2번 나무)
  2.cnt : 남은 이동 횟수 (0~W)
  3.time : 현재 시간 (0~T-1) T초에는 모두 떨어져 있으므로 현재 시간은 T-1까지 가능
  4.value : 현재까지 주운 자두의 최대 개수
• 구하는 답
  $max(DP[pos][cnt][time])$
• 초기값
  $DP[1][W][0]=0$
• 점화식
  • 현재 위치에 자두가 떨어지는 경우
    1. 자리를 바꾸지 않음 : DP[pos][cnt][time+1] = DP[pos][cnt][time] + 1
  • 현재 위치가 아닌 곳에 자두가 떨어지는 경우
    1. 자리를 바꿈 : DP[nextPos][cnt-1][time+1] = max(DP[nextPos][cnt-1][time+1], DP[pos][cnt][time+1] + 1)
    2. 자리를 안바꿈 : DP[pos][cnt][time+1] = DP[pos][cnt][time]

$DP[pos][cnt][time] = value$

https://1004dustkd.tistory.com/entry/C-%EB%B0%B1%EC%A4%80BOJ-2240-%EC%9E%90%EB%91%90%EB%82%98%EB%AC%B4

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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