[Python] BOJ(백준) 22846번 - 인증된 쉬운 게임

링크

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

난이도(solved.ac 참고)

골드3

풀이

처음에는 링고와 칼리가 보는 모니터가 각각 따로 있는 줄 알았다. 그랬는데, 다시 보니까 두명이 같은 모니터를 보고 있었고, 그 상황에서 약수를 더해주는 것이었다.

 

문제가 감이 안와서 유형을 봤는데 게임 이론이었다. 내가 경제시간에 배운 게임이론은 매 상황마다 자신에게 최대한으로 유리한 결정을 내리는 것에 대한 이론으로 기억했다. 일단 트리를 그려봤다.

 

첫 시작은 칼리이므로 칼리는 무조건 1을 더해 2가 될 것이다. 이제 그 다음부터가 시작이다.

각자는 K가 무엇인지 알고있다고 가정했다. 그래야 그에 맞는 최선의 전략을 선택한다는 말이 맞기 때문이다.

K가 2일 경우부터 생각해보자. 그러면 승자는 무조건 칼리이다. 왜냐면 칼리부터 시작하는데 1의 약수는 1 하나밖에 없기 때문이다.

 

이제 K가 3, 4인 경우부터 시작해보자.

칼리의 입장에서는 처음에 무조건 2밖에 선택할 수 없다. 그러면 다음 턴인 링고는 2의 약수인 1 또는 2를 더해줘서 3 또는 4를 선택할 수 있다. 최선의 전략을 선택한다고 했으므로, 링고는 K가 3이라면 3을 선택할 것이고, K가 4라면 4를 선택할 것이다. 그러므로 K가 3과 4일 때 전부 승자는 링고가 된다.

 

다음으로 K가 5인 경우를 보면, 링고의 입장에서는 무조건 3을 선택할 수밖에 없다. 왜냐면 4를 선택한다면 칼리가 5를 선택할 것이고, 그러면 본인은 패배하기 때문이다. 따라서 링고는 3을 선택한다. 이 경우 칼리는 K보다 크면 안되니까 4를 선택할 것이고, 그에 따라 링고는 다시 5를 선택하여 링고가 승리할 것이다.

 

K가 6인 경우는 얘기가 다르다. 링고는 3을 선택하든 4를 선택하든 진다. 왜냐면 3을 선택할 경우 칼리가 4 또는 6 중에 당연히 6을 선택할 것이고, 4를 선택할 경우에도 칼리는 6을 선택하여 끝을 낼 것이기 때문이다. 따라서 K가 6일 때의 승자는 칼리가 된다.

 

사실 맞을 것이라고 생각을 하지 못했던 이유 중 하나는 7부터는 고려해야 할 부분이 많기 때문이었다.

나는 7부터는 어떻게 생각했냐면, 링고의 턴에 K가 들어가지 않았거나 K-1이 들어가 있는 리프 노드는 전부 지웠고 결국 남아있기만 하다면 결국 링고가 질 일은 없겠다고 생각했다. 왜냐면 시작부터 본인의 최적의 전략을 알고 있는 링고는 K-1이 본인의 차례라면 결국 질 것임을 알고 있을 것이라 생각했기 때문이다. K가 들어가있지 않은 경우를 배제한 이유도 마찬가지다.

 

K가 7일 경우는 링고는 첫 차례때 절대 4를 선택하지 않을 것이다. 왜냐면 4를 선택한다면 칼리가 5 -> 링고는 6 -> 칼리는 7을 선택해서 질 것이기 때문이다. 그래서 3을 선택하면, 칼리가 4와 6중에 무엇을 선택하든 링고가 승리한다.

 

K가 8일 경우도 마찬가지. 3번째 칼리의 턴에 8이 있으므로 링고는 무조건 본인의 첫 차례때 3을 선택할 것이고 칼리가 무엇을 선택하든 그 다음 턴에 링고는 모두 8을 보유하고 있으므로 링고가 승리한다.

 

이렇게 계속 꼬리에 꼬리를 물고 시도해봤는데 계속 링고가 이겼다. 그래서 이를 일반화하여 n이 2이거나 6일 경우에만 칼리가 승리하고 나머지는 전부 링고가 승리할 것이라고 생각하여 코드를 작성했고 그대로 맞았다.

 

다이나믹 프로그래밍으로 풀 수 있을 것 같은데, 좀 더 생각을 해봐야겠다.