[삼성] 17825 주사위 윷놀이

시뮬레이션 문제로, 나한테는 삼성 기출 중에 상당히 까다로운 문제인 것 같다

 

시간복잡도 계산 시, 브루트 포스로 말의 순서를 정하면 2^20 * 10번의 주사위 * 최대 5번 = 약 5천만으로 1억 안에 해결할 수 있다. map으로 다음 위치로 하나씩 움직이는 점과 모든 말의 순서를 탐색한다는 점이 시간을 오래 걸리게 했다.

 

 

계속 틀렸던 이유는 dfs가 아닌 브루트포스로 접근했는데, 말이 움직이지도 못한 채 다음 턴으로 넘어가도 이 부분에서 쌓여진 합이 답의 일부분이 되었다. 그리고 브루트포스로 하니 확실히 0.3초가 걸리는, 효율적이지 못한 시간복잡도를 보였다

 

문제: https://www.acmicpc.net/problem/17825

깃허브주소: https://github.com/surinoel/boj/blob/master/17825.cpp

깃허브주소(DFS): https://github.com/surinoel/boj/blob/master/17825_dfs.cpp

 

 

DFS 코드