====== Постройка дороги ====== ===== 풀이 ===== * 짧은 변의 길이가 1이면 그냥 subtraction game이 되므로 긴 변의 길이가 s+1의 배수인지만 확인하면 계산이 가능하다. 하지만, 이 전략은 짧은 변의 길이가 2 이상으로 길어지면 쉽게 적용되지 않는다. 다른 방식으로 찾아보자. * 이 게임은 대칭 전략이 가능한 게임이다. n과 m이 모두 홀수라면, 선공은 첫 턴에 가운데의 1x1칸을 먹은 다음에, 다음턴부터는 상대가 먹는 직사각형의 점대칭 위치의 직사각형을 계속 먹는 것이 가능하다. 이것을 반복하면 결국 먹을 곳이 없어지는 것은 상대가 되므로, 선공이 항상 승리할수 있다. * n과 m이 홀수가 아닐때에도 대칭전략을 구사할수 있다. n과 m중 하나만 짝수라면, 첫턴에 가운데의 2x1칸을 먹으면 된다. 즉 이경우는 s가 2이상이면 선공필승이다. n과 m이 모두 짝수이면 첫턴에 가운데의 2x2칸을 먹어야 한다. 이 경우는 s가 4이상이어야 선공 필승이다. * 만약 s가 작아서 선공이 대칭전략을 구사할수 없는 상황이라면? 물론 대칭 전략을 못쓰더라도 이길수 있는 방법이 있을수도 있지만, 이 게임에서는 이럴때에는 후공 필승이 된다. 방법은 역시 대칭전략인데, 후공이 선공이 둔 위치의 점대칭 위치를 계속 차지하면 된다. * 이렇게 전략을 정리하면, 구현은 간단하다. 시간복잡도도 O(1). ===== 코드 ===== """Solution code for "BOJ 28754. Постройка дороги". - Problem link: https://www.acmicpc.net/problem/28754 - Solution link: http://www.teferi.net/ps/problems/boj/28754 Tags: [game theory] """ def main(): n, m, s = [int(x) for x in input().split()] if n % 2 == m % 2 == 1: print('YES') elif n % 2 == 1 or m % 2 == 1: print('YES' if s >= 2 else 'NO') else: print('YES' if s >= 4 else 'NO') if __name__ == '__main__': main() {{tag>BOJ ps:problems:boj:골드_1}}