#3 Games

스프라그-그런디 정리

애드혹/그리디

 

1) 같은 행동조건

2) 승리 조건이 동일 (상대가 승리하면 내가 패배, 상대가 패배하면 내가 승리)

 

1) dp로 푸는 유형(시간복잡도와 공간복잡도를 고려하지 않는다면 모든 문제에 적용 가능)

dp[x] : x라는 상태에서 선공이 이긴다면 true, 아니라면 false

x에서 갈 수 있는 행동집합들을 모두 살펴보면서, 선공이 지는 상태(즉 상대를 패배하게 만드는 상태) 로

만들 수 있다면 x는 선공이 이길 수 있는 상태인 것이다.

예시 문제

백준 9655 (돌 게임) c++

 

2) 현재 게임판의 상태가 선공이 이기는 게임판인지, 선공이 지는 게임판인지를 알 필요가 없이 항상 승리할 수 있을때

사용 할 수 있다.

다시 말해서 내가 선공일때 현재 게임판이 이기는 게임판이면 그대로 게임하고, 지는 게임판인데, 아무것도 변화시키지

않고 동일하게 상대에게 넘겨줄 수 있다면 내가 이긴다는 논리로 게임의 전략을 세우는 것이다.

예시 문제

백준 12107 (약수 지우기 게임 1) c++