백준) 9655 돌 게임

9655. 돌 게임

문제

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

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

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

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

출력

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

예제 입력 

5

예제 출력 

SK

1. 접근

내가 상근이라면 현재 남은 돌의 갯수를 보고 어떤 선택을 내리는게 완벽한 플레이일까?

1개 남았다면 당연히 1개 가져가면 이긴다.

3개 남았다면 당연히 3개 가져가면 이긴다.

2개 남았다면 1개 가져가고 깨끗하게 지는게 매너플레이다.

4개 남았다면 무슨 짓을 해도 진다.

분명 남은 갯수와 승패에는 연관이 있는 것 같지만 일단 모든 경우를 생각해 보기로 하자.

2-1) 풀이 1

나나 상대나 두 가지 초이스를 할 수 있으므로 이차원 배열 dp[턴][남은 돌]을 정의해보자.

이 배열은 내가 이기는지 지는지 상태를 저장한다.

현재 dp[my][N] 이라면, 나는 1개나 3개를 가져간다. 턴은 상대에게 넘어가고, 그 경우에 내가 이길 수 있는 경우가

하나라도 있다면 나는 그 선택을 완벽하게 할 것이다.

반대로 현재 dp[your][N] 이라면 상대는 1개나 3개를 가져갈 수 있고, 턴은 내것이 될 것이고, 그 경우에 상대가 이길 수 있는 경우가

하나라도 있다면 상대는 그 선택을 완벽하게 할 것이다.

같은 말로, 내가 모두 이기는 경우만 남는다면 나의 승리다. 하나라도 상대가 이기는 경우가 있다면 상대의 승리다.

따라서 우리는 재귀적으로 경우를 확장시켜 보기로 하자.

dp[my][N] 부터 시작해서 dp[my][0], dp[your][0] 까지 확장시킨다.

한 케이스는 두 케이스로 분화된다. (1개를 가져가거나 3개를 가져가거나)

남은 돌이 0개인 채로 턴을 받으면  그 사람의 패배인 것이다.

2-1) 풀이 1. 코드

#include <stdio.h>
#include <string.h>
using namespace std;
 
#define my 1
#define your 0
#define win true
#define lose false
 
int n;
int dp[2][1001];
 
int func(int turn, int remain) {
    if (remain == 0) {
        if (turn == my)
            return dp[turn][remain] = lose;
        if (turn == your)
            return dp[turn][remain] = win;
    }
 
    if (remain < 0) {
        if (turn == my)
            return 1;
        if (turn == your)
            return 0;
    }
 
    if (dp[turn][remain] != -1)
        return dp[turn][remain];
 
    if (turn == my)
        dp[my][remain] =
        func(turn ^ 1, remain - 1) | func(turn ^ 1, remain - 3);
 
    if (turn == your)
        dp[your][remain] =
        func(turn ^ 1, remain - 1) & func(turn ^ 1, remain - 3);
 
    return dp[turn][remain];
}
 
int main() {
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
 
    if (func(1, n) == win)
        puts("SK");
    else
        puts("CY");
 
    return 0;
}

분화시키다보면 remain이 음수가 되버리는 경우가 있다(21행). 그 경우엔 논리식(31, 35행) 에 영향을 주지않는 값을 리턴해주기로 하자.

2-2) 풀이 2

베스킨라벤스 31 게임을 생각해보면 비슷한 이유로 승패가 갈린다.

우리는 초딩때의 경험으로 30, 26, 22, ... , 2를 먹으면 이긴다는 필승법을 알고 있다.

30을 먹으면 상대는 31을 먹고 질 수 밖에 없다.

30을 먹으려면 26을 먹어야 한다. 상대가 몇개를 먹건 나는 30을 먹을 수 있다.

26을 먹으려면 22을 먹어야 한다.

...

이는 한 번에 3개까지 먹을 수 있다는 게임의 특징에서 비롯된다.

마찬가지로 상대가 이길 수 없게 할려면 2개나 4개를 남겨주면 이긴다.

2개를 남기려면 내 턴에 3개나 5개여야 한다.

4개를 남기려면 내 턴에 5개나 7개여야 한다.

...

따라서 승패는 짝수 홀수에 따라 갈린다.

2-2) 풀이 2. 코드

#include <stdio.h>
using namespace std;
 
int n;
 
int main() {
    scanf("%d", &n);
 
    n % 2 == 1 ? puts("SK") : puts("CY");
 
    return 0;
}

3. 후기

이미 기록된 dp배열에 접근할 땐 기존 값을 리턴해주기로 했다. (코드의 28줄)

헌데 이 조건을 함수의 맨 처음에 두었더니 이상한 값이 리턴되었다. 먼저 기저를 작성하고 나중에 기존값 여부를 확인하자.