백준 2342번 Dance Dance Revolution

DP를 이용하여 해결할 수 있다.

n번째에 눌러줘야하는 발판을 now라고 했을 때 n번째에 있을 수 있는 두 발의 상태는 (0, now), ... ,(4, now)이다.

그러면 (0, now)는 n-1번째에 (0, 1), ... , (0, 4) 중에서 0을 누르지 않은 발로 now를 눌러줘야 최소가 된다. 이런 식으로 (4, now)일 때까지의 힘의 최소를 계산해주면 DP로 풀 수 있다.