BOJ 2342 - dance dance revolution

문제 링크

---

https://www.acmicpc.net/problem/2342

문제 해결

---

 1. dp[l][r][stage] : 현재 stage에서 왼발이 l, 오른발이 r에 위치할 때 사용한 최소의 힘

주의할 점 || 생각해볼 점

---

 1. 그리디라고 생각할 수 있지만 항상 현재 해가 최적이 될 수 없다.

     

       아래는 현재 상황에서 가장 적은 힘을 사용해서 움직였을 때의 cost.

     

아래는 현재 상황에서 가장 적은 힘을 사용해서 움직였을 때의 cost. 

 그리디로 해결할 수 없다. 그러므로 DP를 이용해서 해결해야한다.

참고

---

 - 

※ 정확하고 부드러운 태클은 언제나 환영입니다.