# 2342

codesver

Link | 백준 2342번 문제 : Dance Dance Revolution 📌 Code GitHub Repository

aram_father

Problme link: https://www.acmicpc.net/problem/2342 그닥 어렵지 않게 풀 수 있는 DP 문제이다. 아래와 같이 CACHE를 정의하였다. CACHEi[r] = i번째 입력까지 밟고, 오른발이 r, 왼발이 l에 있을 때의 최소 비용 사실 i번째 입력을 밟았다는 사실이 l, r 중 하나가 i번째 입력에 있음을 의미한다. 따라서, 남은 한발만 저장하는 방식으로 조금 더 최적화를 할 수는 있지만 굳이 그럴 것 까지는 없어보여 진행하지 않았다. 점화식은 간단하게, 왼발로 온 경우, 오른 발로 온 경우를 나누어 구해주면 된다.