문제 개요
N개의 원소로 이루어진 배열 A와 이진 문자열 S가 주어졌다고 가정해 봅시다. 두 명의 플레이어가 게임을 진행하며, 각각 0번과 1번으로 번호가 매겨져 있습니다. 초기값이 0인 변수 x가 하나 있고, 게임은 총 N라운드에 걸쳐 진행됩니다.
i번째 라운드에서는 S[i]에 해당하는 번호의 플레이어가 차례를 가지며, 다음 두 가지 행동 중 하나를 선택할 수 있습니다.
- x의 값을 x XOR A[i]로 교체하기
- 아무것도 하지 않기
플레이어 0은 게임이 끝났을 때 x가 0이 되기를 원하고, 플레이어 1은 0이 아닌 값이 되기를 원합니다. 우리가 해야 할 일은 게임 종료 시점에 x가 0이 되는지 여부를 판별하는 것입니다.
입력 예시와 설명
예를 들어 입력이 A = [1, 2], S = "10"이라면 출력은 1이 됩니다. 첫 번째 라운드에서 플레이어 1이 x를 0 XOR 1 = 1로 만들면, 이후 플레이어 0이 어떤 선택을 하더라도 x는 절대 0이 될 수 없기 때문입니다. 즉, 결과값 1은 최종적으로 x가 0이 아니게 된다는 것을 의미합니다.
해결 접근 방식
이 문제는 선형 대수의 관점에서 효율적으로 풀 수 있습니다. 배열 judge는 사실상 GF(2) 위에서의 선형 기저(linear basis) 역할을 수행하며, 각 숫자를 기저에 삽입하면서 해당 값이 기존 값들의 XOR 조합으로 0이 될 수 있는지, 즉 독립적인 값인지를 판단합니다.
핵심 아이디어는 배열의 뒤쪽 라운드부터 앞쪽으로 순회하는 것입니다. 자신의 차례에 기저에 삽입된 후에도 0이 되지 않는, 즉 독립적인 값을 확보할 수 있는 플레이어가 최종 결과를 좌우하게 되며, 그러한 차례를 가진 사람이 플레이어 1이라면 결과는 1이 됩니다.
알고리즘 의사 코드
이 문제를 해결하기 위해 다음 단계를 따릅니다.
N := A의 크기
크기가 60인 배열 judge 정의
z := 0
judge 배열을 0으로 채움
n := N - 1로 초기화하고, 0 <= n 조건에서 n을 1씩 감소시키며 반복:
x := A[n]
다음 블록을 무조건 반복:
x가 0과 같으면:
루프 탈출
y := x
I := -1
i := 0으로 초기화하고, i < 60 조건에서 i를 1씩 증가시키며 반복:
y mod 2가 1과 같으면:
I := i
y := y / 2
judge[I]가 0과 같으면:
judge[I] := x
루프 탈출
x := x XOR judge[I]
S[n]이 '0'과 같지 않으면:
x가 0과 같지 않으면:
z := 1
z 반환
C++ 구현 예제
보다 정확한 이해를 위해 아래의 C++ 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, string S){
int N = A.size();
int judge[60];
int z = 0;
fill(judge, judge + 60, 0);
for (int n = N - 1; 0 <= n; n--){
int x = A[n];
while (1){
if (x == 0)
break;
int y = x;
int I = -1;
for (int i = 0; i < 60; i++){
if (y % 2 == 1)
I = i;
y /= 2;
}
if (judge[I] == 0){
judge[I] = x;
break;
}
x ^= judge[I];
}
if (S[n] != '0'){
if (x != 0)
z = 1;
}
}
return z;
}
int main(){
vector<int> A = { 1, 2 };
string S = "10";
cout << solve(A, S) << endl;
}
실행 결과
입력
{ 1, 2 }, "10"
출력
1
복잡도 분석
각 원소마다 최대 60비트에 대해 기저 삽입 연산을 수행하므로, 전체 시간 복잡도는 O(N × 60)입니다. 비트 길이가 상수로 제한되어 있기 때문에 실질적으로 O(N)에 가까운 매우 효율적인 알고리즘이라고 할 수 있습니다.