[BOJ_9655] 돌 게임

 

📌 문제 링크: https://www.acmicpc.net/problem/9655

9655번: 돌 게임

 

✅ 내 풀이(Success) :

 

🧐 Review:

 문제 분류에 DP가 있어서 풀어본 문제인데, 위 코드를 보면 이게 과연 실버 난이도의 문제인지 의심이 들 정도이다.(아마도 추후에 브론즈로 내려갈 가능성이 있지 않을까?) 하지만 돌의 개수인 n에 따라서 누가 이기는지 구하기 위해 모든 경우의 수를 나열하면서 규칙성을 찾는 과정이 결코 단순한 과정은 아니었다. SK와 CY가 자신이 승리하기 위해 본인의 경우의 수 뿐만 아니라 상대방의 경우의 수도 같이 고려해야 되는 과정이 필요했기 때문이다.

 문제를 풀고 나서 해당 문제의 분류에 있는 '게임 이론'에 대해서 검색을 해보니 이런 유형의 문제에 해당하는 알고리즘인 '미니 맥스 알고리즘'에 대해서 알게 되었다. 자세한 내용은 아래의 링크로 대체하겠다.

 

🚩 Idea:

 - 두 명의 플레이어(SK, CY)중에서 항상 자신이 게임에서 이길 수 있는 최선의 수를 둔다고 생각하면서 경우의 수를 계산한다.

 

🏷️ Reference:

 - 미니 맥스 알고리즘 : https://m.blog.naver.com/msnayana/80155230751