[BaekJoon] #11869 - 님블 [Java][C++]

문제 링크

---

1. 아이디어

$1 \times N$ 보드에 놓인 동전을 왼쪽으로 한 칸 이상 옮기며 마지막 동전을 0번 칸으로 옮기는 사람이 이기는 님블에서 승자를 구하는 문제다. 동전 하나를 그 칸 번호만큼 돌이 쌓인 더미로 보면 동전을 왼쪽으로 옮기는 것은 그 더미에서 돌을 하나 이상 제거하는 것과 같고, 0번 칸의 동전은 더 이상 움직일 수 없는 빈 더미에 대응한다. 한 칸에 동전이 여러 개 있어도 각 동전은 서로 영향을 주지 않으므로 칸 번호를 돌 개수로 바꾸면 님 게임과 완전히 같은 게임이 된다. 결국 모든 동전의 칸 번호를 XOR한 Nim-Sum이 0이 아니면 선공이, 0이면 후공이 이긴다.

---

2. 복잡도

접근	시간	공간
풀이	$O(M)$	$O(1)$

($M$ = 입력값 m)

---

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 nimsum = 0;

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (m-- > 0) {
            nimsum ^= Integer.parseInt(st.nextToken());
        }

        if (nimsum != 0) {
            System.out.println("koosaga");
        } else {
            System.out.println("cubelover");
        }
    }
}

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

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

    int nimsum = 0;

    int m;
    cin >> m;

    while (m--) {
        int p;
        cin >> p;
        nimsum ^= p;
    }

    if (nimsum) {
        cout << "koosaga";
    } else {
        cout << "cubelover";
    }
}

---