[백준 24678] 파이썬 : 돌무더기 게임 1

24678

제 1회 실버컵 A

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

24678번: 돌무더기 게임 1

[정답]

import sys
T = int(sys.stdin.readline())
for t in range(T):
    odd = 0
    even = 0
    a = list(map(int, sys.stdin.readline().split()))
    for i in range(3):
        if a[i] % 2 == 0:
            even += 1
        else:
            odd += 1
    if (even == 3 or even ==2):
       print('R')
    else:
       print('B')

.

.

.

[풀이]

이기기 위한 최선의 수는 큰 값의 돌무더기 2개를 계속 선택하는 것이다.

 

이를 적용하여 T = 200,000  x, y, z <= 10^9 임에도 그냥 brute force로

for문을 이용하여 하나하나 더하고 빼고 해봤다.

결과는 당연히 시간초과 였다.

 

더 간단한 규칙을 찾아야함을 느꼈고

수기로 하나씩 적어가며 수가 움직이는 규칙을 살펴보았다.

어떤 수들의 조합이든

마지막에는 0, 0, 1 또는 0, 0, 2 되어 더이상 시행할 수 없게된다.

 

세 수가 짝수인지 홀수인지 즉,

짝짝짝

짝짝홀

짝홀홀

홀홀홀

에 따라서 마지막 수로 몇번의 시행(돌무더기 고르기)을 거치는지가 결정된다.

 

짝짝짝, 짝짝홀의 경우 짝수번의 시행을 거쳐 마지막에 도착하므로 승자는 R

짝홀홀, 홀홀홀의 경우 홀수번의 시행을 거쳐 마지막에 도착하므로 승자는 B

 

결국 수가 홀수인지 짝수인지로 구분하면 답이 나오는 문제가 되어버린다.

 

p.s.

처음 참여해본 백준 대회.

문제 난이도들이 어마무시했다.

그나마 풀 수 있을 거 같은 A번을 끄적끄적여봤다.

운 좋게 방법을 찾았고

좋은 풀이는 아닌거 같아 아쉬웠지만

대회 문제를 풀었다는 것에 크나큰 성취감을 느꼈다.

 

한문제 풀었더니 80등 했다. 

ㅎㅎ..