16895번: 님 게임 3
구사과와 큐브러버가 님 게임을 하고 있다. 님 게임은 돌을 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진
www.acmicpc.net
Sprague-Grundy Theorem..
재밌다.
O(MN^2) 로 브루트포스 돌리면서 님 합이 0이 된다면 ans에 1 더하는 방식으로 풀었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
for j in range(1, a[i]+1):
p = a[i] - j
for k in range(n):
if i == k: continue
p ^= a[k]
if p == 0:
ans += 1
print(ans)
|
cs |
테케가 약해서 뚫리는데, 원래는 배열 P의 수들을 미리 XOR해두어 풀어야된다.
다시풀음
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
n = int(input())
a = list(map(int, input().split()))
t = 0
for i in a:
t^=i
ans = 0
for i in range(n):
for j in range(1, a[i]+1):
p = a[i] - j
p ^= a[i]
p ^= t
if p == 0:
ans += 1
print(ans)
|
cs |
'백준 문제풀이' 카테고리의 다른 글
| 백준 17291 - 새끼치기 [Python] (0) | 2021.04.08 |
|---|---|
| 백준 1321 - 군인 [Python] (0) | 2021.04.08 |
| 백준 17371 - 이사 [Python] (0) | 2021.04.01 |
| 백준 13263 - 나무 자르기 [Python] (0) | 2021.03.29 |
| 백준 8911 - 거북이 [Python] (0) | 2021.03.29 |