백준 9657. 돌 게임 3

https://www.acmicpc.net/problem/9657

9657번: 돌 게임 3

 

bool d[N] : true시 돌이 N개 일때 해당  턴인 사람이 이김. 

d[1] = true

d[2] = false 

d[3] = true 

d[4] = true 

 

두명 모두 최적의 수를 두기 때문에, d[i-1], d[i-3], d[i-4] 중 하나라도 false라면 d[i]는 true가 된다.

 

무슨 말이냐면 돌이 6개일때 상근이 턴이라고 생각해보자.

1	2	3	4	5	6	7
true	false	true	true	true	true

6-1 = 5 

d[5] = true이다. 

즉 돌이 6개 있을때 현재 턴인 사람이 이긴다는 뜻이다.  

 

6-3 = 3

d[3] = true이다.

즉 돌이 3개 있을때 현재 턴인 사람이 이긴다는 뜻이다.

 

6-4 = 2

d[2] = false이다.

즉 돌이 2개 있을때 현재 턴인 사람이 진다는 뜻이다.

 

상근이와 창영이 모두 최적의 수를 두기 때문에, 돌이 6개 있을때 상근이가 4개를 가져가서 돌이 2개 남도록 한다면, d[2] = false이므로 다음 턴인 창영이는 지게 된다. 즉 상근이가 이기게 된다.