[BOJ] 백준 16882번 : 카드 게임 (JAVA)

문제

구사과와 큐브러버가 카드 게임을 하려고 한다. 카드 게임은 정수가 적혀있는 카드 N개를 일렬로 나열한 상태에서 시작되며, i번째 카드에 적혀있는 수는 Ai이다.

 

게임은 턴을 번갈아가면서 진행되고, 구사과가 먼저 게임을 시작한다. 각 턴은 다음과 같이 이루어져 있다.

 

 

- 카드를 하나 고르고 제거한다. 이 때, 고른 카드에 적힌 수보다 작은 수가 적혀있는 카드도 모두 제거한다.

- 즉, i번째 카드를 고른 경우에는 i번째 카드와 Aj < Ai를 만족하는 모든 j번째 카드도 제거한다.

 

 

카드가 모두 제거된 경우에는 게임이 끝나며, 더 이상 제거할 카드가 없는 사람이 게임을 지게 된다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람이 누구인지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 카드의 수 N이 주어진다. 둘째 줄에는 카드에 적힌 수 Ai가 주어진다.

 

 

출력

구사과가 이기는 경우에는 "koosaga", 큐브러버가 이기는 경우에는 "cubelover"를 출력한다.

 

 

제한

- 1 ≤ N ≤ 105

- 1 ≤ Ai ≤ 105

 

 

풀이

간단한 게임 이론 문제였습니다.

 

 

특정 카드를 제거하였을 때, 그 수보다 작은 수의 카드를 모두 제거하는 것이 게임의 규칙이었습니다.

선공이 가장 큰 수를 지우면 이길 것 같으나, 같은 수의 카드가 여러 개 있을 수 있다는 변수를 잘 따져야 했습니다.

따라서, 같은 수의 카드가 몇 개가 있는지에 따라 케이스를 분류해 보겠습니다.

 

 

(1) 모든 카드가 짝수 개 있는 경우

간단한 사례인 "1 1"부터 봅시다.

선공이 1을 뽑고, 후공이 1을 뽑으면 선공이 패배합니다.

 

 

수를 좀 더 늘려서 "1 1 2 2"를 봅시다.

선공이 2를 가져가게 되면 앞에 1도 모두 사라지지만, 후공이 나머지 2를 가져가면서 선공이 패배합니다.

반대로, 선공이 1을 가져가게 되면 후공은 1 또는 2를 가져갈 수 있는데, 1을 가져가면 선공이 패배합니다.

즉, 후공은 카드의 개수를 짝수로 만들어서 선공에게 넘겨주어 이길 수 있습니다.

 

따라서, 같은 수의 카드가 짝수 개 있으면, 후공이 필승합니다.

 

 

(2) 모든 카드가 홀수 개 있는 경우

이 경우는 "1 3 5 7"과 같이 모든 숫자의 카드가 단 한 장만 존재하는 것입니다.

선공은 당연히 가장 큰 수를 뽑음으로써 모든 카드를 제거할 수 있으므로 선공이 필승합니다.

 

 

(3) 카드가 홀수, 짝수 개 혼합되어 있는 경우

이 경우는 "1 2 2 3 3 3"과 같이 숫자의 카드가 홀수와 짝수 개가 존재하는 것입니다.

선공이 3을 가져가면, 남은 카드가 "3 3"이 되는데 각자 1개씩 가져가야하므로 선공이 이깁니다.

즉, 선공은 카드의 개수를 짝수 개로 만들어서 후공에게 넘길 수 있게 됩니다.

 

선공은 자신의 턴에 카드의 상태가 (1) 케이스면 패배하는데, 후공이 자신의 턴에 카드의 상태가 (1) 케이스가 되도록 강제하여 선공이 이길 수 있는 것입니다.

 

 

 

(1) ~ (3) 케이스를 통하여, 모든 카드가 짝수 개일 경우만 후공이 이기고, 나머지는 선공이 이기게 됩니다.

다시 말하면, 같은 카드의 개수가 홀수 개인 케이스가 하나라도 있으면 선공이 이기는 것입니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.