백준 2342 - dance dance revoution (Python)

BOJ PS/Python 2022. 12. 16. 11:14

2342번: Dance Dance Revolution

입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마

www.acmicpc.net

bfs로 풀다가 막혀서 dp로 풀게 된 문제. bfs로도 분명 가능은 한데, 메모리 초과가 뜬다. visited 처리를 잘 못해주어서이다.

처음 풀었던 풀이는 이랬다.

즉 heap을 만들어 최대한 비용이 적은 움직임을 먼저 하여 가장 먼저 끝난 것을 출력하는 것이었다.

다만 이렇게 할 경우 중복되는 것들을 잡아낼 수 없어 heap에 자꾸 값이 들어가고, 그러니 결국 메모리 초과가 뜬다.

dp로 풀면 이렇게 풀게 된다.

즉 시작점부터 왼발, 오른발로 디딜 수 있는 모든 경우의 수를 dp에 갱신한다.

왼발로 디디면 오른발이 그대로고, 오른발로 디디면 왼발이 그대로라는 점을 이용한다.

생각 생각