백준 26937 Circular Barn python 풀이

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

26973번: Circular Barn

 

 

일단 N = 1인 경우를 생각해보자. 편의상 Farmer John을 FJ라 하고, Farmer Nhoj를 FN이라 부르겠다.

a(i) = 1, 2, 3인 경우는 FJ가 이기고, 4인 경우는 FN이 이긴다. FN이 이기는 경우는 i에 대해, i - j의 값이 FN이 지는 경우면 반대로 i에서는 이길 수 있으니, 이러한 j가 존재하면 된다. 존재하지 않으면 FN이 이길 것 이다.

5, 7은 FJ가 이기고, 6 - 2 = 4이기 때문에, 6 또한 FJ가 이긴다. 8인 경우는, 8 - 1, 8 - 2, 8 - 3, 8 - 5, 8 - 7 모두 안되기에, FN이 이긴다.

뭔가 4의 배수일 땐 FN이 이기고, 나머지는 FJ가 이기는 것 같다. 이 사실을 증명해보자.

1 ~ 4까지를 기저 조건이라 하자. $4\times i+a(0<a<4)$, 일 때는 a를 빼줄 수 있기에, FJ가 이긴다. $4\times i$인 경우는, 1 또는 소수를 빼도 다른 4의 배수에 도달할 수 없기에 무조건 FJ가 지고 FN이 이긴다. 귀납법으로 증명해줄 수 있다.

 

$N=1$인 경우의 문제를 풀었으니, 이제 원래 문제를 풀어보자.

$i\equiv 0mod4$ 인 경우는 FJ가 지기 위한 최대 횟수를, 나머지 경우에는 이기기 위한 최소 횟수를 안다고 해보자.

그렇다면 $a(i$)를 왼쪽에서부터 훑으면서, 그 값이 지금까지 구한 값의 최소라면, 그 문제의 정답을 알 수 있다.

 

이러한 값들은 dp를 통해 구해줄 수 있다.

$i\equiv 0mod4$인 $i$에 대해서는, $dp(i)=max(dp(i-1),dp(i-2),dp(i-3))+1$ 이 될 것이다. 

나머지 경우는, $i\equiv p(i)mod4$인 가장 큰 $p(i)$에 대해, $dp(i-p(i))+1$ 이 될 것이다. 이러한 $p(i)$의 값은, 이분탐색을 통해 구하거나, 에라토테네스의 체를 돌리면서 찾아줄 수 있다. 

나머지 경우에 $i\equiv p(i)mod4$ 인 $p(i)$를 찾아주는 이유는,$i-p(i)\equiv 0mod4$가 될 것이기 때문이다.

 

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline

n = 5 * int(1e6) + 1
prime = []
isp = [1] * (n + 1)
for i in range(2, n + 1):
    if isp[i]: prime.append(i)
    for p in prime:
        if i * p > n: break
        isp[i * p] = 0
        if i % p == 0: break
isp[0] = 0
isp[1] = 1
p = [[] for _ in range(4)]
p[1] = [1]
for i in prime: p[i % 4].append(i)
dp = [0] * n
for i in range(1, n):
    if isp[i]: dp[i] = 1
    elif i % 4:
        j = bl(p[i % 4], i)
        j -= 1
        dp[i] = dp[i - p[i % 4][j]] + 1
    else:
        dp[i] = max(dp[i - 1], dp[i - 2], dp[i - 3]) + 1
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    tmp = float('inf')
    ans = "Farmer John"
    for i in a:
        if dp[i] // 2 < tmp:
            tmp = dp[i] // 2
            if i % 4: ans = 'Farmer John'
            else: ans = 'Farmer Nhoj'
    print(ans)

되게 애드혹적인? 게임이론 dp 문제였다. 

X를 a(i)의 범위라 할 때, 

$O(X+XlogX+\sum N)=O(XlogX+\sum N)$ 에 풀 수 있다.