백준) 9657 돌 게임 3

9657. 돌 게임 3

문제

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

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

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

입력

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

출력

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

예제 입력 

6

예제 출력 

SK

1-1) 풀이 1

돌 게임 1(http://js1jj2sk3.tistory.com/30)과 비슷한 문제다. 4개도 가져갈 수 있다는 조건만 추가해주면 된다.

#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) | func(turn ^ 1, remain - 4);
 
    if (turn == your)
        dp[your][remain] =
        func(turn ^ 1, remain - 1) & func(turn ^ 1, remain - 3) & func(turn ^ 1, remain - 4);
 
    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;
}

1-2) 풀이 2 

0개라면 이미졌다.

1개면 이긴다.

2개면 진다.

3개면 이긴다.

4개면 이긴다.

까지가 기본적인 전략이고, http://js1jj2sk3.tistory.com/30 에서 설명한 추가 전략대로면,

5개면 완벽한 선택으로 상대에게 1, 3, 4 상태를 만들어 주지 않기 위해 3개를 가져가야 한다.

6개면 동일하게 4개를 가져가야 한다.

7개면 1개를 가져가든(나머지 6) 3개를 가져가든(나머지 4) 4개를 가져가든(나머지 3) 상대의 필승이다.

7개일 때부터는 이미 가져갈 수 있는 세 가지 전략에 대해 결과를 이미 알고 있다.

따라서 0개 ~ 6개의 결과가 반복될 것을 알 수 있다. (패/승/패/승/승/승/승)