11695번: 표 게임

https://www.acmicpc.net/problem/11695

i번째 행에 있는 돌의 합을 si라 놓자. 그러면 이들을 이용하는 님게임으로 생각할 수 있다.
si를 모두 xor 시켰을 때 0이면 선수 승리, 1이면 후수 승리.

#include<cstdio>
int n, m;
long long s, r;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        s = 0;
        for (int j = 0, x; j < m; j++) scanf("%d", &x), s += x;
        r ^= s;
    }
    puts(r ? "august14" : "ainta");
    return 0;
}

5386번: Doubloon Game

https://www.acmicpc.net/problem/5386

#include<cstdio>
int s, k, t;
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d", &s, &k);
        if (k & 1) printf("%d\n", s & 1);
        else {
            s %= k + 1;
            printf("%d\n", s / k*k + s % 2);
        }
    }
    return 0;
}

11062번: Card Game

https://www.acmicpc.net/problem/11062

c[i]: i번째 카드에 쓰인 수
dp[i][j]: j-i+1, j-i+2, ..., j번째 카드가 남았을 때 선수 플레이어가 만들 수 있는 최대 합
dp[i][j] = sum(c[k]: j-i<k<=j) - min(dp[i-1][j-1],dp[i-1][j])

시간복잡도는 테스트 케이스마다 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
int s[1001], n, t;
int main() {
    for (scanf("%d", &t); t--;) {
        int dp[1001] = {};
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", s + i), s[i] += s[i - 1];
        for (int i = 1; i <= n; i++) for (int j = n; j >= i; j--) dp[j] = s[j] - s[j - i] - min(dp[j - 1], dp[j]);
        printf("%d\n", dp[n]);
    }
    return 0;
}

10563번: Number Game

https://www.acmicpc.net/problem/10563

#include<cstdio>
#include<cstring>
int t, n, dp[100][100][100], a[100], l, r, lc, rc, g;
int f(int s, int e, int c) {
    if (c < 0 || s > g || e < g || s == e) return 1;
    int &ret = dp[s][e][c];
    if (!~ret) ret = !f(s + 1, e, s == l ? lc + c : c) | !f(s, e - 1, e == r ? rc + c : c) | !f(s, e, c - 1);
    return ret;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        lc = 0; rc = 0;
        memset(dp, -1, sizeof(dp));
        for (int i = 0; i < n; i++) {
            scanf("%d", a + i);
            if (a[i] == 1) l = r = g = i;
        }
        for (; l && a[l - 1] > a[l];) l--;
        for (; r < n - 1 && a[r] < a[r + 1];) r++;
        int i = l, j = r;
        for (; i && a[i - 1] < a[i]; i--) lc++;
        for (; j < n - 1 && a[j] > a[j + 1]; j++) rc++;
        puts(f(l, r, i + n - 1 - j) ? "Alice" : "Bob");
    }
    return 0;
}

9656번: 돌 게임 2

https://www.acmicpc.net/problem/9656


$O(1)$

매 턴마다 남아 있는 돌 수의 홀짝성이 바뀌게 된다. 처음 개수가 홀수이면 CY 짝수이면 SK가 이긴다.

#include<cstdio>
int n;
int main() {
    scanf("%d", &n);
    puts(n & 1 ? "CY" : "SK");
    return 0;
}

9659번: 돌 게임 5

https://www.acmicpc.net/problem/9659


$O(1)$

매 턴마다 남아 있는 돌 수의 홀짝성이 바뀌게 된다. 처음 개수가 짝수이면 CY 짝수이면 SK가 이긴다.

#include<cstdio>
int n;
int main() {
    scanf("%d", &n);
    puts(n & 1 ? "SK" : "CY");
    return 0;
}

9655번: 돌 게임

https://www.acmicpc.net/problem/9655


$O(1)$

매 턴마다 남아 있는 돌 수의 홀짝성이 바뀌게 된다. 처음 개수가 홀수이면 SK 짝수이면 CY가 이긴다.

#include<cstdio>
int n;
int main() {
    scanf("%d", &n);
    puts(n & 1 ? "SK" : "CY");
    return 0;
}