문제 개요
서로 다른 양의 정수로 이루어진 배열 A가 있다고 가정해 봅시다. 두 명의 플레이어 P와 Q가 이 배열로 게임을 진행합니다. 각 턴마다 플레이어는 배열에서 두 수 a와 b를 골라 그 차이의 절댓값 |a − b|를 확인하고, 해당 값이 배열에 존재하지 않으면 새로운 숫자로 추가합니다. 더 이상 새로운 숫자를 추가할 수 없게 된 플레이어가 패배합니다. 플레이어 P가 항상 먼저 시작한다고 할 때, 최종 승자가 누구인지 구하는 것이 목표입니다.
예를 들어 입력이 A = [8, 9, 10]이라면 출력은 P가 됩니다.
해결 전략: 최대공약수(GCD) 활용
이 문제의 핵심 열쇠는 바로 최대공약수(GCD)입니다. 배열에 추가되는 모든 숫자는 기존 두 수의 차이이므로, 결국 등장할 수 있는 모든 숫자는 배열 전체의 GCD인 g의 배수가 됩니다. 따라서 게임이 종료되는 시점에는 배열에 g부터 최댓값 max_val 사이의 g의 모든 배수가 채워져 있게 됩니다.
즉, 게임 전체의 총 턴 수는 다음과 같이 계산할 수 있습니다.
total = (max_val ÷ g) − n
이 값이 홀수이면 마지막 수를 놓는 주체는 선공인 P이므로 P가 승리하고, 짝수이면 Q가 승리합니다.
알고리즘 단계
- n := 배열의 크기
- g := arr[0], max_val := arr[0]
- i를 1부터 n−1까지 반복:
- g := gcd(g, arr[i])
- max_val := max(max_val, arr[i])
- total := (max_val / g) − n
- total이 홀수이면 'P' 반환
- 그렇지 않으면 'Q' 반환
Python 구현 예제
from math import gcd
def who_is_the_winner(arr) :
n = len(arr)
g = arr[0]
max_val = arr[0]
for i in range(1, n) :
g = gcd(g, arr[i])
max_val = max(max_val, arr[i])
total = (max_val / g) - n
if (total % 2 == 1) :
return 'P'
return 'Q'
arr = [8,9,10]
print(who_is_the_winner(arr))
입력
[8,9,10]
출력
P
동작 원리 살펴보기
예제 배열 [8, 9, 10]에 위 로직을 적용해 보겠습니다. 세 수의 최대공약수 g는 1이고, 최댓값 max_val은 10, 배열의 크기 n은 3입니다. 따라서 total = (10 ÷ 1) − 3 = 7이 되며, 7은 홀수이므로 마지막 수를 추가하는 플레이어는 선공인 P가 됩니다. 실제로 게임을 진행하면 배열에는 1부터 10까지의 모든 정수가 순차적으로 채워지며, 일곱 번째(마지막) 수를 놓는 것은 P이므로 Q는 더 이상 움직일 수 없어 패배하게 됩니다.
이처럼 매 턴을 직접 시뮬레이션하지 않고도 GCD 하나만으로 총 게임 턴 수를 O(n) 시간에 계산해 승자를 즉시 판별할 수 있습니다.