[BOJ 15490] 즐거운 게임

문제

---

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

풀이

---

pypy3으로 제출해서 4360ms로 통과했다.

시간제한 1초에 * 2 + 3 보너스를 받고 겨우 통과한 것이다.

애초에 맞은 사람 48명 중에 파이썬 계열로 통과한 사람이 나밖에 없었다.

그도 그럴 것이 MLE 3번, TLE 2번을 받고 Bottom-Up 방식으로 구현해서야 통과할 수 있었다.

우선 양 끝 지점에서 1개 또는 2개를 선택할 수 있으므로 (lower bound, upper bound), 그리고 현재 내가 고른 수들의 합의 홀짝이 정해지면 부분 문제가 성립한다.

마지막 요소가 없다면 구간이 주어졌을 때 총합이 홀수가 돼야 이기는지 짝수가 돼야 이기는지 모르기 때문이다.

마지막 요소로 충분한 이유는 lower bound부터 upper bound까지의 구간 합의 홀짝과 전체 합의 홀짝은 홀수라는 점을 알고 있기 때문이다.

결론적으로 내가 지금까지 고른 수들의 총합의 홀짝을 flag, lower bound부터 upper bound까지 구간 합의 홀짝을 total이라 했을 때, 상대방이 고른 수들의 총합의 홀짝은 (flag + total + 1) % 2이며, 내가 택할 수 있는 4가지 경우 중 하나라도 상대방을 무조건 지게 할 수 있는 선택지가 존재한다면 이기는 것이다.

코드

---

import sys

n = int(sys.stdin.readline())
num = list(map(lambda x: int(x) % 2, sys.stdin.readline().split()))
acc = [0]
for i in range(n):
    acc.append((acc[-1] + num[i]) % 2)
dp = [[[-1, -1] for _ in range(n)] for __ in range(n)]

for k in range(n):
    for i in range(n - k):
        j = i + k
        if k == 0:
            dp[i][i][0] = int(0 == num[i])
            dp[i][i][1] = int(1 == num[i])
        
        elif k == 1:
            dp[i][j][0] = 1
            dp[i][j][1] = num[i] | num[j]
        
        else:
            total = acc[j + 1] - acc[i]
            for flag in [0, 1]:
                you = (flag + total + 1) % 2
                res = 1
                res *= dp[i + 1][j][you]
                res *= dp[i + 2][j][you]
                res *= dp[i][j - 2][you]
                res *= dp[i][j - 1][you]
                res ^= 1

                dp[i][j][flag] = res

print(['No', 'Yes'][dp[0][-1][0]])