[코딩테스트 연습] 땅따먹기

 

programmers.co.kr/learn/courses/30/lessons/12913

---

dp + 슬라이딩 윈도우로 해결할 수 있습니다.

 

현재 칸에서 어떤 칸을 밟을지 결정할 때는 오직 '이전 칸'의 정보만 가지고 있으면 되므로

 

dp테이블은 dp[2][N] 크기만 가져도 됩니다.

 

dp 점화식은 dp[i+1][N] = max(dp[i][0], dp[i][1], dp[i][2], ... , dp[i][N-1]) + score[i+1][N] 입니다.

 

즉, N열이 아닌 이전 칸 중에 최댓값 + 이번 칸의 값을 더하면 점화식이 됩니다.

---

코드: github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG12913.cc