알고리즘 - Python / 백준 - 9661번 : 돌 게임 7

9661번: 돌 게임 7 (acmicpc.net)

9661번: 돌 게임 7

 

---

풀이

• 서로 돌을 n개씩 번갈아 가며 가져가다가 가져갈 돌이 없다면 패배하는 게임이다.
• 백준의 돌 게임 문제들은 게임이론과 관련된 문제로 개인적으로 상당히 좋아하는 문제다.
• 이전에 돌 게임6 에 관한 풀이도 작성하였다.

 

알고리즘 - Python / 백준 - 9660번 : 돌 게임 6 (tistory.com)

알고리즘 - Python / 백준 - 9660번 : 돌 게임 6

 

 

• 돌 게임 스타일의 게임 이론 문제를 풀 때 내가 가장 먼저 시도하는 방법은 모두 다 해보는 것이다.
• 왜냐하면 돌 게임 같은 스타일의 문제는 DP 적인 요소가 없지 않아 있기 때문에 DP처럼 모두 써보는 것이 문제의 감을 잡기에 상당히 좋기 때문이다.
• 일단 왜 DP 적인 요소가 있는지 생각해보면 N = 7 인 경우를 생각해보자.
• N = 7 일때 상근이가 먼저 돌을 가져가므로 1개 또는 4개 가져갈 것이다.
• 그렇다면 N = 1 ~ 6 까지의 결과를 이미 알고 있다면 , 문제는 창영이부터 시작하면서 N = 6 또는 N = 3 인 문제로 바뀐 것이다.
• 앞쪽의 결과들은 서로 최선의 플레이에서 발생하는 결과들 이므로 고정된 결과들 이다.
• 그렇다면 예를 들어 N = 3 일 때 상근이가 이겼고 , N = 6 일 때 창영이가 이겼다면 , N = 3의 경우는 먼저 하는 사람이 무조건 이기고 , N = 6의 경우는 무조건 뒤에 하는 사람이 이긴다는 이야기가 된다.
• 상근이도 이를 알고 있으므로 , 돌 1개를 가져가 N = 6 을 만들어 창영이가 N = 6 상황에서 선공을 가져가게 만들 것이다. 
• 이전에 구한 결과들은 어떻게 하던지 순서와 N이 정해지면 바꿀 수 없는 결과 이므로 , 상근이가 돌 1개를 가져가면 N = 7 인 상황에서도 상근이가 무조건 이기게 된다. ( 위의 예시는 이 문제와 관련 없이 쓴 것이다. )
• 즉 N의 이전 상황이 현재 N의 승 , 패에 연관이 있다는 것이고 대부분의 돌 게임 문제는 이렇게 나열하다 보면 규칙이 보인다.
• 이번에도 나열해 보니 다음과 같은 결과들이 보였다. ( 나는 손으로 풀었지만 DP적 풀이로 코딩해서 나열해보는 것도 괜찮을 듯 싶다. )
• 1 - SK / 2 - CY / 3 - SK / 4 - SK / 5 - CY / 6 - SK / 7 - CY / 8 - SK / 9 - SK / 10 - CY....
• 패턴을 쭉 읽어보니 S-C-S-S-C / S-C-S-S-C 같은 패턴이 보이는 듯하다.
• 5로 나눈 나머지가 0,1,2,3,4 일 때 , 답이 나오는 패턴이 있다고 생각하였고 , 제출해보았더니 맞았다.
• 좀 더 수학적인 풀이는 다른 블로그를 참고하길 바란다. ( 나도 언제나 돌 게임은 풀고 나서 내 생각이 맞았는지 다른 수학적 풀이를 찾아본다.)

 

import sys
n = int(sys.stdin.readline())
if n % 5 == 0 or n % 5 == 2:
    print("CY")
else:
    print("SK")

---