[BaekJoon] #16895 - 님 게임 3 [Java][C++]

문제 링크

---

1. 아이디어

님 게임에서 선공이 이기기 위해 첫 턴에 할 수 있는 방법의 수를 구하는 문제다. 선공이 이기려면 후공에게 Nim-Sum이 0인 상태를 넘겨야 하므로 첫 턴에 Nim-Sum을 0으로 만드는 수를 세면 된다. 전체 Nim-Sum을 $\text{nim} = p_1 \oplus p_2 \oplus \dots \oplus p_n$이라 하면 더미 $p_i$를 $x$개로 줄였을 때의 Nim-Sum은 $\text{nim} \oplus p_i \oplus x$이고, 이것이 0이 되려면 $x = \text{nim} \oplus p_i$여야 하므로 더미마다 가능한 $x$가 하나로 정해진다. 돌은 제거만 할 수 있어서 $x < p_i$여야 하므로 $(\text{nim} \oplus p_i) < p_i$인 더미의 수가 답이다. 처음부터 $\text{nim}$이 0이면 $x = p_i$라서 조건을 만족하는 더미가 없고, 이는 후공이 이기는 상태이므로 답이 0인 것과 맞아떨어진다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = 입력값 n)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int nimsum = 0;

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nimsum ^= arr[i] = Integer.parseInt(st.nextToken());
        }

        int cnt = 0;
        for (int p : arr) {
            if ((p ^ nimsum) < p) cnt++;
        }

        System.out.println(cnt);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    int nimsum = 0;

    vector<int> v(n);
    for (int& p : v) cin >> p;
    for (int p : v) nimsum ^= p;

    int cnt = 0;
    for (int p : v) {
        if ((p ^ nimsum) < p) cnt++;
    }

    cout << cnt;
}

---