선공(N/도훈) 후공(S/지훈) 

처음에 게임판이 비어있으면(N>=2) 무조건 지훈이 이김

[1]
게임판 크기가 홀수이면, 어떻게든 SNSNSN? 되게 만들 수 있다.

?????????

????N????

??SN?????

NSN??????

?NSNS????

[2]
게임판 크기가 짝수이면 S..S 그룹만 안만들면 됨

??????????

??????N???

?????SN???

??N??SN???

?SN??SN???

?SN??SN??N

?SN???SNSN

?SN??NSNSN

[일반화?]
N..N 그룹 수 = nn
N..S 그룹 수 = ns
S..N 그룹 수 = sn
S..S 그룹 수 = ss

N의 턴일 때 nn < ss여야 N이 이김.
턴 이후 상황 : [1] nn+=1 / [2] ns-=1, nn+=1 / [3] nn+=1, sn-=1 ...
즉, 모든 턴이 nn+=1 또는 ss-=1을 유발함.

--특이 상황--
처음 게임판이 정해져있는 경우, N?S 및 S?N이 인위적으로 있음
=> N?S, S?N을 한 그룹으로 간주해도 됨

??N?SN?S?? => ns=1

??N?SN??SN => nn=1 sn=1

??N?SNS?NS?? => ns=1

??N?SNS??NSN => nn=1 ns=1

1. N이 첫 턴 못 놓는 상황 : S(지훈)이 이김
2. N이 첫 턴 놓았을 때 S가 못 놓는 상황 : N(도훈)이 이김
3. N, S가 모두 첫 턴 가능한 상황 : nn, ss 개수에 따라 승자 결정됨

[증명방법]
nn < ss 이고 S가 턴을 쓸 공간이 있으면 N은 무조건 턴을 쓸 수 있다.

* 처음에 N?S, S?N을 모두 묶었으므로, N?..?S가 있다면 ?가 2개 이상이라 N이 턴 사용 가능
* S..S가 반드시 있는데, S 옆칸에 N을 놓지 못하는 경우는 S가 마지막인 경우밖에 없음
* N을 놓지 못하면 여유 공간이 없다는 의미이므로 S를 놓지도 못함

<case work>
nn=ss일 때 N이 이기는 특수 케이스
NS...

S.NSN???SN.S : N이 이길 수 없음

S.NSN???SN.S : N이 못이김

S.NSN???????SN.S : 

[기타]
N..S 특징 : N을 오른쪽으로 당기는게 불가능

N???S : N 턴수 = S 턴수
S??N : N 턴수 = S 턴수
N??N : N 턴수 = S 턴수 - 1
S??S : N 턴수 = S 턴수 + 1

????? : N 턴수 = S 턴수
N???? : ?가 1,2,4~이면 N 턴수 = S 턴수, ?가 3이면 N 턴수 = S 턴수 + 1
S???? : 


NS..N..