BOJ_11694_님 게임 (Java)

[Platinum II] 님 게임 - 11694

문제 링크

성능 요약

메모리: 14288 KB, 시간: 108 ms

분류

게임 이론, 스프라그–그런디 정리

제출 일자

2024년 11월 18일 15:51:18

문제 설명

koosaga와 cubelover가 님 게임을 하고 있다. 님 게임은 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진행한다. 각 사람의 턴이 되면, 돌이 있는 돌 더미를 하나 선택하고, 그 돌 더미에서 돌을 하나 이상 제거한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 지게 된다.

게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다.

입력

첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 100)이 주어진다.

둘째 줄에는 각 돌 더미에 쌓여있는 돌의 개수 P_i (1 ≤ P_i ≤ 2×10⁹)가 주어진다.

출력

koosaga가 이기는 경우에는 'koosaga'를, cubelover가 이기는 경우에는 'cubelover'를 출력한다.

문제 풀이

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
//		br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		int first = Integer.parseInt(st.nextToken());
		
		if(N==1) {
			System.out.println(first==1? "cubelover" : "koosaga");
			return;
		}
		
		int XOR = first;
		boolean flag = (first == 1); // 모든 숫자가 1인지 check
		
		for(int i = 1; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			XOR ^= num;
			if(num != 1) flag = false;
		}
		if(flag == true) bw.write(N%2==1? "cubelover" : "koosaga");
		else bw.write(XOR==0? "cubelover" : "koosaga");
		
		bw.flush();
		bw.close();
		br.close();
	}
}