[백준 / BOJ] 2342 Dance Dance Revolution

문제

출처 : www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

승환이는 DDR게임을 할려고한다.

 

중앙, 위, 왼쪽, 아래, 오른쪽 순서로 0, 1, 2, 3, 4 라고 할때, 승환이가 눌러야할 방향이 순서대로 주어진다.

한 위치에서 다른 위치로 발을 이동시킬때드는 힘의 크기가 다를때, 모든 방향을 누를때 드는 최소힘의 크기를 구하는 문제다.

 

풀이

BFS나 DP로 풀리는 문제다.

 

왼쪽발을 움직여서 해당 숫자를 누르는게 당장은 이득일수있어도 나중에는 아닐수있기때문에, 어떤 발을 움직여서 눌러야하는지 판단하는건 불가능하다. 따라서, 모든 경우를 다 봐줘야한다고 생각했다.

 

BFS로 이미 도달한 상태를 두번봐주지 않는식으로 구현했다.

 

입력받은 수열들의 한칸 한칸을 idx라고 했을때, 

idx까지 도달했을때 발의 상태를 체크하고, 최소힘을 저장해줬다. 따라서 모든경우를 중복없이 봐주기위해선 check배열을 3차원으로 만들어줘야한다.

(현재 왼쪽발의 위치와 오른쪽발의 위치를 고려하지않고 수열의 크기만 갖고 최소힘을 저장하면 위에서 말한 반례가 나올수있다.)

check[왼쪽발의 위치][오른쪽발의 위치][현재 인덱스] = 최소힘

 

BFS는

 

1. 현재 발의 상태에서 왼쪽발을 움직이는 경우

-> (check[움직인왼쪽발][오른쪽발][다음인덱스] 과 현재힘 + 움직이는데 드는힘) 을 비교해주며 현재힘 + 움직이는데 드는힘이 더 작을때만 큐 에 넣어줬다.  

2. 현재 발의 상태에서 오른쪽발을 움직이는경우

-> 왼쪽발과 마찬가지로 했는데, 오른쪽발을 움직인경우로 구현하면된다.

 

이때, 왼쪽발과 오른쪽발이 겹치지않도록 주의해야한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2342%20Dance%20Dance%20Revolution/main.cpp

devxb/JJUNalgo