두 명의 플레이어 X와 Y가 n개의 숫자로 이루어진 배열을 가지고 게임을 진행하는 상황을 생각해 봅시다. 각 플레이어는 배열에서 숫자를 선택하게 되며, 우리의 목표는 게임이 시작되기 전에 최종 승자를 미리 예측하는 것입니다.
게임 규칙
- 플레이어 X가 승리하려면, X가 선택한 숫자들의 합과 Y가 선택한 숫자들의 합의 절대 차이가 4의 배수여야 합니다.
- 절대 차이가 4로 나누어 떨어지지 않으면 플레이어 Y가 승리합니다.
- 게임은 항상 플레이어 X부터 시작합니다.
예제로 이해하기
입력: a[] = {3, 6, 9, 12}
출력: X
설명:
X가 3과 6을 선택
Y가 12와 9를 선택
|3 + 6 − (12 + 9)| = |9 − 21| = 12 → 12는 4의 배수이므로 X 승리
해결 접근 방법
이 문제의 핵심은 배열의 각 원소를 4로 나눈 나머지에 주목하는 것입니다. 두 합의 차이가 4의 배수인지 여부는 각 숫자가 어떤 나머지 클래스(0, 1, 2, 3)에 속하는지에 따라 결정되기 때문입니다.
판정 절차는 다음과 같습니다.
- 배열의 모든 원소에 대해 arr[i] % 4 값을 계산합니다.
- 나머지가 0, 1, 2, 3인 경우의 등장 횟수를 각각 셉니다.
- 네 개의 나머지 값이 모두 짝수 번 등장했다면 X가 승리하고, 하나라도 홀수 번 등장하면 Y가 승리합니다.
즉, count[0], count[1], count[2], count[3]이 모두 짝수일 때 |X의 합 − Y의 합|이 4로 나누어떨어짐이 보장되므로, 전체 배열을 한 번만 순회하면 승자를 즉시 판별할 수 있습니다.
C++ 구현 코드
#include <iostream>
using namespace std;
int playGame(int a[], int n) {
int count[4] = {0, 0, 0, 0};
for (int i = 0; i < n; i++) {
count[a[i] % 4]++; // 나머지별 등장 횟수 누적
}
// 네 나머지 그룹의 개수가 모두 짝수인지 확인
if (count[0] % 2 == 0 && count[1] % 2 == 0 &&
count[2] % 2 == 0 && count[3] % 2 == 0)
return 1; // X 승리
else
return 2; // Y 승리
}
int main() {
int a[] = { 4, 8, 5, 9 };
int n = sizeof(a) / sizeof(a[0]);
cout << "Game Started!\n";
if (playGame(a, n) == 1)
cout << "X wins the Game";
else
cout << "Y wins the Game";
return 0;
}
실행 결과
Game Started! X wins the Game
코드 설명
playGame 함수는 크기 4의 count 배열을 사용해 각 나머지 값(0~3)의 등장 횟수를 누적합니다. 이후 네 개의 카운트가 모두 짝수인지 검사하여, 짝수라면 1(X 승리)을, 그렇지 않다면 2(Y 승리)를 반환합니다.
예제 배열 {4, 8, 5, 9}의 경우 각 원소를 4로 나눈 나머지는 0, 0, 1, 1이므로 count = [2, 2, 0, 0]이 됩니다. 모든 값이 짝수이므로 프로그램은 X의 승리를 출력합니다.
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
- 공간 복잡도: O(1) — 크기가 고정된 카운트 배열만 사용합니다.