| 시간 제한 | 메모리 제한 |
| 1초 | 512MB |
문제
두 명의 학생이 1이상 n이하의 정수를 외치는 게임을 하고 있다. 첫 번째 학생이 먼저 정수를 외친 후 두 명의 학생이 교대로 정수를 외친다. 이전 학생이 외친 정수가 a이면 현재 학생은 (a + 1)이상 (a + k)이하의 정수를 외쳐야 한다. 맨 처음 첫 번째 학생은 1이상 k이하의 정수를 외쳐야 한다. 추가로, 두 명의 학생이 외칠 수 없는 정수 목록이 주어지고, 두 명의 학생은 목록에 있는 정수를 외칠 수 없다. 마지막에 정수를 못 외치는 학생이 게임을 진다. 현재 학생이 외칠 수 있는 정수가 여러 개이면, 외칠 수 있는 정수 중 하나를 외친다. 두 명의 학생이 규칙에 맞게 플레이했을 때, 첫 번째 학생이 이기면 1을 출력하고 두 번째 학생이 이기면 0을 출력한다.
입력
첫 번째 줄에 n과 k가 공백을 사이에 두고 순서대로 주어진다.
두 번째 줄에 두 명의 학생이 외칠 수 없는 서로 다른 정수가 빈칸을 사이에 두고 오름차순으로 주어진다.
- 1 ≤ n ≤ 100,000
- 1 ≤ k ≤ 100
- 두 명의 학생이 외칠 수 없는 서로 다른 정수 목록의 개수는 1보다 크거나 같고 n보다 작거나 같다.
- 두 명의 학생이 외칠 수 없는 정수는 1보다 크거나 같고 n보다 작거나 같은 양의 정수이다.
출력
첫 번째 줄에 첫 번째 학생이 이기면 1을 출력하고, 두 번째 학생이 이기면 0을 출력한다.
풀이
님 (게임) - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전.
ko.wikipedia.org
배스킨라빈스(게임)
게임의 참여자들은 차례를 정해 1부터 31까지의 수를 순차적으로 부른다. 한번에 1~3개까지 수를 연달아 부를 수
namu.wiki
이 유명한 게임의 1대1 필승법은 외쳐도 괜찮은 숫자 중 가장 마지막 숫자를 외치는 것이다. n = 100이라면 100을 말하는 사람이 이긴다. 그럼 어떡하면 100을 말할 수 있을까? 게임을 순차적으로 진행하지 말고 승리하는 시점에서 거꾸로 올라가보자. k = 5인 상황을 가정해보자.
내가 95를 말하고 상대방에게 턴을 넘겼다. 그러면 상대방은 95+1~95+5까지를 외칠 수 있으므로 100을 외칠 수 있게 된다. 그러므로 나는 94를 외쳐야 한다. 만약 93을 외친다면?
상대방은 필승패인 94를 외치고 나에게 턴을 넘길 것이다. 그럼 나는 어떤 수를 말해도 100을 놓칠 수 밖에 없다. 따라서 마지막 숫자가 필승패가 되고, 그로부터 k+1 이전의 수가 순차적으로 필승패가 된다. 100, 94, 88, 82, ... 10, 4. 그런데 여기서는 문제를 한 번 꼬았다. 외칠 수 없는 숫자가 존재하는 것. 이런 경우는 k+1 이전의 수를 외칠 수 없기도 하다. 좀 더 본질적으로 문제를 분석해보자. 다음 입력을 기준으로 생각해보자.
12 3
2 4 5 8 11 12
빨간색은 외칠 수 없는 숫자들이다. 필승패는 10으로 시작된다. 필승패는 파란색으로 표시하겠다.
나는 10을 외쳐야 한다. 상대 입장에서 생각해보자. 항상 최선의 플레이를 하기 때문에 상대 역시 10을 외치는 것이 목표다. 그렇다면 내가 상대에게 7 또는 9로 턴을 넘긴다면 상대는 10을 외칠 수 있다. 그 이유는 7로부터 +1~+3까지의 범위 내에 필승패가 존재하기 때문이다. 따라서 가장 마지막에 있는 필승패로부터 거꾸로 탐색을 시도하며 +1~+k 범위 내에 필승패의 존재 여부를 살펴보면 된다.
- 필승패가 존재하는 경우, 그 숫자를 외치면 상대가 필승패를 외칠 수 있다.
- 필승패가 존재하지 않는 경우, 그 숫자를 외치면 상대가 필승패를 외칠 수 없고 반드시 내가 다음 필승패를 외치게 된다.
이렇게 두 가지 경우로 나뉘므로 어렵지 않게 필승패들을 찾아낼 수 있다. 한 가지 조심해야 하는 부분은 k개 이상의 연속된 외칠 수 없는 숫자 구간이 존재한다면 그런 경우, 필승패가 더 당겨져야 한다.
이런 경우, 4, 5, 6 구간을 뛰어넘어서 숫자를 외칠 수 없으므로 3을 외치면 다음 턴의 사람은 외칠 숫자가 없다. 따라서 가장 마지막이 아니라 k개 이상의 숫자가 연속된 구간의 직전 숫자 3이 필승패가 된다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
n, k = map(int, input().split())
block = list(map(int, input().split()))
dp = [0] * (n + 1)
# 외칠 수 없는 수 = 2
for b in block: dp[b] = 2
l = n # 필승패의 위치
cnt = k # cnt가 k 이상이면서 dp[i] = 0인 경우 i가 새로운 필승패가 됨
# dp[-1] = 0 인 경우 곧바로 필승패가 되어야 하기 때문에
# cnt의 초기 값을 k로 지정함
# 가장 작은 필승패 찾기
for i in range(n, -1, -1):
if dp[i]: cnt += 1
else:
if cnt >= k:
l = i
cnt = 0
dp[l] = 1
for i in range(l - 1, 0, -1):
if dp[i] == 2: continue
# i+1부터 i+k까지 살피되, i+k가 n을 넘는 경우는 n까지만 살펴본다.
for j in range(i + 1, min(i + k, n) + 1):
if dp[j] == 1:
dp[i] = 0
break
else: dp[i] = 1
# 1부터 k까지 살피되, k가 n을 넘는 경우는 n까지만 살펴본다.
# 해당 구간에 필승패가 있다면 선공 승리, 없다면 후공 승리
for i in range(1, min(n, k) + 1):
if dp[i] == 1:
return 1
else: return 0
print(solution())
