BOJ 31584. 전구 게임

옛날 함수컵에 나온 인터랙티브 문제로, 굉장히 쉬운 문제이지만 흥미로워서 글을 써 본다.

링크

문제

$N$개의 스위치가 일렬로 있고, 스위치 사이에 각각 하나씩 총 $N-1$개의 전구가 있다. $N$은 짝수다.

처음에는 모든 전구가 꺼져 있다. A와 B 두 사람이 게임을 한다. 총 $N/2$턴으로 진행되며, 각 턴은 다음과 같이 진행된다.

• 먼저 A가 아직까지 안 눌러진 스위치 하나를 누른다.
• 다음으로 B가 아직까지 안 눌러진 스위치 하나를 누른다.
• 이때 두 스위치 사이의 전구들은 켜짐/꺼짐 순서가 반전된다.

B는 마지막에 켜진 전구가 꺼진 전구보다 더 많아야 이긴다. B의 필승 전략을 찾아라.

풀이

풀이는 굉장히 전형적인 유형이지만, 처음 보는 경우 굉장히 신기한 유형이다.

스위치들을 인접한 것끼리 두 개씩 묶자. 이러면 총 $N/2$개의 그룹이 생긴다.

A가 어떤 스위치를 누르면 B는 해당 그룹에 있는 다른 스위치를 누르면 된다. 이때 그 사이에 있는 전구 하나가 켜질 것이다.

$N/2$턴 각각에 스위치들로 생기는 구간이 모두 독립적이므로, 각 턴에 전구가 정확히 하나씩 켜질 것이고, 마지막에는 홀수 번째 전구들은 켜지고, 짝수 번째 전구들은 꺼져 있을 것이다. 전구가 항상 홀수 개이므로 이러면 B가 무조건 이긴다.

더 흥미로운 관찰

사실 조금 더 관찰해보면 이 게임은 어떤 방식으로 플레이하든 최종 상태가 고정되어 있다는 것을 알 수 있다.

각각의 스위치를 누적 합 (또는 누적 xor)의 관점에서 바라볼 수 있다. A와 B가 스위치를 하나씩 선택할 때, 다음과 같은 일이 일어난다.

• 두 스위치 사이에 있는 전구들의 상태가 반전된다.

그런데 위 동작을 다음과 같이 해석할 수도 있다.

• 먼저 A가 누른 스위치 오른쪽에 있는 전구들의 상태가 전부 반전되고,
• B가 누른 스위치 오른쪽에 있는 전구들의 상태가 전부 반전된다.

따라서 사실 스위치를 누가 눌렀냐는 별로 중요하지 않다. 마찬가지로 스위치가 어떤 턴에 눌렸는지도 별로 중요하지 않다. 결국 모든 스위치는 한 번씩 눌리고, 홀수 번째 전구들은 홀수 번, 짝수 번째 전구들은 짝수 번 반전된다. 그래서 위 풀이 섹션에서 설명한 최종 상태가 사실 항상 일어날 것이고, A와 B가 어떤 스위치를 골라도 항상 이긴다.

사실 여기까지 알았더라도, 구현이 가장 간단한 풀이는 위의 풀이라서, 그냥 위의 풀이를 짜는 게 낫다.

코드

XOR 연산을 이용하면 굉장히 간단하게 구현할 수 있다.

#include "bulb.h"

void Init(int N){}

int MakeTurn(int M){
    return ((M-1)^1)+1;
}