[9660] 돌 게임 6

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

9660 - 돌 게임 6

본문

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 $N$이 주어진다. ($1 \leq N \leq 1\,000\,000\,000\,000$)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

문제만 놓고보면 dp문제다. 1부터 시작하여 $N$의 최댓값까지 경우의 수를 셀 때, 내가 필승으로 이길 수 있는 상황과 이길 수 없는 상황이 계산되기 때문에 한 사람에 대한 결과를 기록해놓고 사용할 수 있다. 게임이론 문제기도 하다.

다만 문제가 $N$의 범위가 너무 크다는 것. dp배열을 만들 수가 없다. 시간도 1초밖에 주어지지 않으므로, 이 문제를 해결하기 위해서는 dp를 이용하지 말고 규칙을 찾는 것이 더 효율적이다.

규칙을 찾아보자. 먼저 시작하는 사람을 A, 다음 사람을 B라고 하자.

돌의 개수	승자	경우의 수
1	A	1
2	B	1-1
3	A	3
4	A	4
5	A	3-1-1
6	A	4-1-1
7	B	4-3
8	A	1-4-3
9	B	3-4-1-1

1과 3, 4일때는 항상 먼저 시작한 사람이 이긴다. 2일 때는 상대방이 이기는 경우밖에 없다.

5와 6일때는, 먼저 시작한 사람이 이길 수 있다. 이 상황에서는 상대방이 이길 수 밖에 없는 상황인 2로 상대방을 내몰 수 있기 때문이다.

7일 때는 상대방이 이기는 경우밖에 없다. 먼저 시작하는 사람은 7에서 시작한다면 만들 수 있는 상황이 3, 4, 6이 된다. 하지만 위 상황 모두 그 상황에서 먼저 시작하는 사람이 이기는 경우이다. 즉, “7부터 시작했다면 이기는 경우의 수가 없다”는 뜻.

그리고 놀랍게도, 이 게임의 주기는 7마다 반복된다. 8의 상황에서는 상대방을 7로 내몰 수 있으므로 승리, 9의 상황에서는 5, 6, 8 모두 본인이 승리하는 상황이므로 항상 패배할 수밖에 없다. 10의 경우 9의 상황으로 상대방을 내몰 수 있고, 이 상황이 반복되며 주기가 7인 상황이 계속된다.

그래서, $N$을 $7$로 나누었을 때의 나머지가 0 또는 2라면 상대방이 승리하고, 아닌 상황 전부에서는 본인이 이길 수 있다는 말로 풀이된다.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2019 / 9 / 3

#include <stdio.h>

int main() {
    long long n;
    scanf("%lld", &n);
    if (( n % 7 == 0 ) || ( n % 7 == 2 ))
        printf("CY");
    else
        printf("SK");
    return 0;
}