시간 복잡도

 

1. 문제 : 백준 - 주사위 윷놀이

www.acmicpc.net/problem/17825

 

2. 틀린 이유 : 주어진 이동횟수 또한 바뀔 것이라 생각해서 10! * 4^10의 시간복잡도를 계산하고도 완전 탐색으로 풀려고 했다. 실제로는 4^10만 계산해서 완전탐색으로 풀 수 있는 문제이지만 풀이를 구상하기 전에 시간복잡도를 먼저 계산하고 맞는 풀이인지 검토하려는 노력이 필요하다.

 

3. key idea : 4^10(1,048,576), 10!(3,628,800) -> 대충 계산할 수 있는 능력 다 백만 안쪽으로 계산된다.

 

4. 알아두면 좋을 것 :

(1) 실제로 10! * 4^10으로 해당 문제가 나왔다면 어떻게 계산해야될까? -> dp를 이용하면 될듯한데,,,조금 더 생각해보기

(2020.12.30. 추가) TSP -> Bitmask DP 아이디어로 풀 수 있다.

TSP -> Bitmask DP란 각각의 노드를 방문했는지 안했는지만 표시해두고 현재 위치를 기록해서 min 값을 저장하면 n!의 문제를 2^n * n으로 줄일 수 있음.

해당 아이디어를 빌려와서 각각의 노드가 선택한 이동 횟수를 2^10, 현재 위치를 84개로 나누어서 dp로 싹다 저장한 다음 4^10으로 각 이동횟수가 어떤 노드를 통해 선택되는지를 Brute Force로 계산하면 시간 안에 문제를 풀 수 있다.