문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

두 사람이 Misère Nim 게임을 하고 있다. 이 게임의 기본적인 규칙은 아래와 같다.

• 게임은 0부터 n - 1까지 번호가 매겨진 n개의 돌 무더기로 시작한다. 각 무더기 i는 s[i]개의 돌을 가지고 있다. 이때 i는 0보다 크거나 같고 n보다 작다.
• 플레이어들은 번갈아가면서 진행한다. 각 플레이 동안 현재 플레이어는 하나의 무더기에서 1개 또는 더 많은 돌을 제거해야한다.
• 마지막 돌을 제거한 플레이거가 게임에 지게 된다.

n의 값과 각 돌 무더기의 개수가 주어질때, 게임에서 이기는 사람이 첫 번째 플레이어인지 두 번째 플레이어인지 찾아라. 만약 첫 번째 플레이어가 이기면 First 아니라면 Second를 출력해라. 두 플레이어는 최선의 플레이를 한다.

Example

s = [1, 1, 1]

이 경우, 플레이어 1은 하나의 무더기를 선택하고, 플레이어 2는 하나의 무더기를 선택하고, 다시 플레이어 1은 마지막 하나의 무더기를 선택한다. 플레이어 2가 승리하므로 Second를 반환한다.

s = [1, 2, 2]

최적의 플레이할 때 플레이어2가 이길 방법은 없다. 예를 들어, 플레이어 1이 첫 번째 무더기를 선택한다. 만약 플레이어 2가 다른 무더기에서 1개를 제거하면 플레이어 1은 2개가 남은 무더기를 선택할 것이다. 만약 플레이어 2가 2개가 있는 무더기를 선택한다면, 플레이어 1은 돌 무더기에서 1개만 제거하고 마지막에 플레이거 2가 돌을 제거하게 된다. First를 반환한다.

Function Description

misereNim 함수를 완성해라.
misereNim 함수는 아래와 같은 매개변수를 가지고 있다.

• int s[n]: 각 돌 무더기의 수

Returns

• String: First 또는 Second

Constraints

• 1 <= T <= 100
• 1 <= n <= 100
• 1 <= s[i] <= 10^9

All Code

public static String misereNim(List<Integer> s) {

	int n = s.size();

	if (n == 1) {
		return s.get(0) > 1 ? "First" : "Second";
	}

	int total = s.get(0);
	int xor = s.get(0);

	for (int i = 1; i < n; i++) {
		total += s.get(i);
		xor ^= s.get(i);
	}

	if (total == n) {
		return total % 2 == 0 ? "First" : "Second";
	}

	return xor > 0 ? "First" : "Second";
}