[Python 3] BOJ 25419 정수를 끝까지 외치자

https://www.acmicpc.net/problem/25419

이번 문제는 Nim Game의 일종인 '정수를 끝까지 외치자' 문제를 풀어보았다.

처음에 가졌던 생각은, '돌 게임 https://www.acmicpc.net/problem/9655' 문제와 술 게임인 '배스킨라빈스 31'과 유사하다는 생각을 했었다.

모두 님 게임과 같은 메커니즘을 가진 문제이다.

먼저, 학생 1이 우선권을 가져서 먼저 정수를 부를 수 있다.

부를 수 있는 수는 1부터 K까지이다.

이후 학생 2는 학생 1이 부른 숫자에 + 1 부터 +k까지의 정수를 불러야 한다.

그리고, 마지막 정수를 부르는 학생이 승리하는 문제이다.

문제에 조금 애매한 표현이 있는데, '두 학생이 규칙에 맞게 플레이했을 때'이다. 각 학생이 부를 수 있는 정수들의 수는 굉장히 많고, 마음대로 고를 수 있다. 하지만, 그 중에서 학생들은 '최적의 수'를 불러야 한다. 여기서 말하는 최적의 수란, '상대가 어떠한 수를 내든, 상대가 무조건 패배하게끔 한다'를 만족시키는 수이다.

배스킨 라빈스 문제를 예시로 들면, 31을 말하는 사람이 지는 게임이다.

내가 26을 부르면,

상대방이 27을 부르면, 난 28, 29, 30을 부르면 된다.

상대방이 27, 28을 부르면, 난 29, 30을 부르면 된다.

상대방이 27, 28, 29를 부르면, 난 30을 부르면 된다.

즉, 나의 최적의 수는 30인 것이고, 30을 반드시 부르기 위해서는 26을 불러야 한다는 것이다.

이렇게 필승 숫자를 dp table을 이용하여 표현해보자.

내 승리를 반드시 만들어 주는 수를 dp[i]=1로 표현하면 된다.

즉, dp[30]=1, dp[26]=1이고, 나의 승리가 확실시되지 않는 (상대방의 플레이로 승리를 뺏길 수 있는 경우)는 모두 dp[i]=0으로 표현한다.

n,k=map(int,input().split())
data=list(map(int,input().split()))
dp=list(0 for _ in range(n+1))
for i in data:
    dp[i]=1e10
maxNum=n
for i in range(1,n+1):
    if i+k>n:
        break
    if all(x==1e10 for x in dp[i:i+k]):
        maxNum=i-1
        break

for i in range(maxNum,0,-1):
    if dp[i]==1e10:
        continue
    allzero=1
    for j in range(i+1,i+k+1):
        if j>n:
            break
        if dp[j]==1e10:
            continue
        elif dp[j]==1:
            allzero=0
            break
    dp[i]=allzero
for i in range(1,min(n,k)+1):
    if dp[i]==1:
        print(1)
        exit(0)
print(0)

이제 코드를 설명하겠다.

먼저, 부르면 안 되는 번호를 dp에 1e10의 값으로 부여하였다.

그리고 우리가 최종적으로 불러야 할 제일 큰 숫자를 찾았다. 당연히 n이면 제일 좋겠지만, k의 범위가 정해져있고 부르면 안되는 숫자가 연속적으로 연결되어 있을 경우, 큰 숫자까지 경기가 이어지지 못한다.

그러므로, 연속적으로 1e10로 채워져 있는 구간을 찾아서, 그 전 인덱스를 maxNum으로 저장한다.

이후, maxNum부터 1번째 인덱스까지 역순으로 탐색하면서,

현재 인덱스 +1 부터 현재 인덱스 + k 번째 인덱스까지 보면서 dp의 값 중 1이 있는지 확인한다.

이 중 dp[j]=1이라 함은, 최적의 해를 상대에게 넘겨준다는 의미이다.

그러므로, 이런 경우는 dp[i]의 값이 0이 된다.

처음 1부터 k까지의 숫자 중 학생 1이 최적으로 골라서 이길 수 있는 해가 있으면, 학생 1의 승리이고,
만약 그런 값이 존재하지 않다면, 학생 2의 승리일 것이므로,
1부터 k까지 dp의 값이 1이라면 1을, 아니라면 0을 출력한다.