문제 개요
두 개의 숫자 k와 target이 주어진다고 가정해 보겠습니다. Amal과 Bimal이라는 두 플레이어가 게임을 진행하며, 각 라운드마다 플레이어는 1부터 k 사이의 숫자를 하나 골라 현재 총합에 더합니다. 이때 총합은 0에서 시작합니다. 누구든 총합을 target 이상으로 만들면 그 플레이어가 승리합니다.
Amal이 항상 먼저 플레이한다고 할 때, 두 플레이어 모두 최적의 전략으로 게임한다는 조건 하에 Amal이 반드시 승리하도록 만들 수 있는지 확인해야 합니다.
예를 들어 k = 5, target = 10인 경우 출력은 True입니다. Amal이 첫 턴에 4를 선택하면, Bimal이 이후 1부터 5 중 어떤 숫자를 선택하더라도 Amal은 다음 턴에 적절한 숫자(6에서 Bimal이 고른 수를 뺀 값)를 골라 총합을 정확히 10으로 만들 수 있기 때문입니다.
해결 전략
이 문제는 게임 이론의 대표적인 유형인 '목표 숫자 도달 게임'과 같습니다. 핵심 아이디어는 다음과 같습니다.
- 한 턴에 더할 수 있는 수의 범위가 1부터 k까지이므로, 두 플레이어가 한 번씩 번갈아 플레이하면 총합은 최소 1씩, 최대 k씩 증가합니다.
- (k + 1)은 한 라운드(두 플레이어의 턴) 동안 총합을 정확히 맞출 수 있는 특별한 값입니다. 상대가 x를 더하면 나는 (k + 1 − x)를 더해 라운드의 합을 k + 1로 고정할 수 있습니다.
- 따라서 target이 (k + 1)로 나누어떨어지지 않으면, 선공인 Amal이 첫 턴에 target을 (k + 1)로 나눈 나머지만큼 더해 (k + 1)의 배수 지점을 선점할 수 있습니다. 이후에는 매 라운드마다 합이 k + 1이 되도록 맞추며 결국 target에 먼저 도달합니다.
- 반대로 target이 (k + 1)로 나누어떨어진다면, 후공인 Bimal이 위 전략을 그대로 사용할 수 있으므로 Amal은 강제로 승리할 수 없습니다.
이 논리를 정리하면 다음과 같습니다.
- target % (k + 1)이 0이 아니면 → True 반환 (선공 승리 가능)
- 그렇지 않으면 → False 반환 (선공 승리 불가능)
구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
def solve(k, target):
return target % (k + 1) != 0
k = 5
target = 10
print(solve(k, target))
입력
5, 10
출력
True
동작 원리 분석
k = 5일 때 k + 1 = 6이고, target = 10을 6으로 나눈 나머지는 4입니다. 나머지가 0이 아니므로 함수는 True를 반환합니다. 실제로 Amal이 첫 턴에 4를 선택하면 총합은 4가 되고, 이후 매 라운드마다 Bimal이 고른 수와 합쳐서 6이 되도록 Amal이 대응하면 총합은 4 → 10 순으로 진행되어 Amal이 정확히 10에 도달하며 승리합니다.
이 알고리즘은 단순한 나눗셈 연산만 수행하므로 시간 복잡도는 O(1), 공간 복잡도 역시 O(1)로 매우 효율적입니다.