[2342] Dance Dance Revolution

코나미의 마지막 불꽃

 

 

2342번: Dance Dance Revolution

(이 문제 풀다가 추억 돋아서 BEMANI REMIX 듣다가 살짝 해 멘 문제)

 

DP는 DP인데 재귀를 사용하는 DP입니다.

 

처음에는 왼발 오른발 위치를 기억하고 i번째 일을 마쳤을 때 값을 기준으로 점화식을 놓으려다가 막혀서

재귀 함수를 돌리되 memozation을 이용하는 것으로 풀었습니다.

 

가능한 case의 수는 지시사항이 N개 있을 때 2^N개입니다. 이를 다 처리하려면 답이 없습니다.

일단 처음 지시사항을 실시할 때 왼발이나 오른발이나 같으니 가지치기를 통해 줄이더라도 여전히 큰 수가 나옵니다.

그런데 여기서 생각해볼 점이 i번째 일을 마쳤을 때 왼발과 오른발 위치가 같다면 나중에 걸리는 힘의 크기는 당연히 같을 겁니다.

따라서 1) 이를 memozation으로 저장하기 위해 memo[l][r][i] 로 저장을 하고,

더 나아가 생각해보면 2) 왼발과 오른발 위치를 바꾸더라도 나중에 걸리는 힘의 크기는 같겠죠.

따라서 memo[r][l][i] 역시 같은 값으로 저장해주고 계산할 때 써주게 되면 계산을 그나마 빠르게 할 수 있을 겁니다.

처음에는 얼마나 줄일 수 있겠어 생각했는데 지시사항이 4가지 종류밖에 없고 덕분에 중복되는 경우가 많아서 그런지 solve 할 수 있었습니다.

 

소스

 

https://github.com/Hesh0629/solved_boj_problems_in_army/blob/main/2342.cpp