목록게임 dp (1)
블로그 옮겼습니다
Codeforces Round #406 (Div. 2) C. Berzerk
http://codeforces.com/contest/787/problem/C 이 문제는 게임 dp 문제인데 Nim 게임과 같은 게임 dp 문제와 다른점이 하나 있다. Nim 게임에서는 보통 두 플레이어가 매 턴 마다 돌을 한개 이상씩 가져가기 때문에 돌이 점점 줄어들고, 그렇기 때문에 돌의 개수와 현재 차례인 플레이어, 이 두가지로 하나의 상태를 정의할 때 그래프로 표현해 보면 노드 A에서 노드 B로 가는 경로가 여러개가 있을 수는 있지만 한번 방문한 노드는 다시 방문되어지지 않는다 (즉, 사이클이 없다) 하지만 이 게임에서는 monster 가 움직일 칸 수를 번갈아서 결정하다 보면 게임 판이 원의 형태로 되어있기 때문에 현재 차례인 플레이어와 현재 monster의 위치가 다시 같은 상태가 돌아올 수도..
Algorithm/Problem Solving
2017. 3. 29. 20:07