사용자 도구

사이트 도구


ps:problems:boj:28754

Постройка дороги

ps
링크acmicpc.net/…
출처BOJ
문제 번호28754
문제명Постройка дороги
레벨골드 1
분류

게임 이론

시간복잡도O(1)
사용한 언어Python 3.11
제출기록31120KB / 44ms
최고기록44ms
해결날짜2024/04/16

풀이

  • 짧은 변의 길이가 1이면 그냥 subtraction game이 되므로 긴 변의 길이가 s+1의 배수인지만 확인하면 계산이 가능하다. 하지만, 이 전략은 짧은 변의 길이가 2 이상으로 길어지면 쉽게 적용되지 않는다. 다른 방식으로 찾아보자.
  • 이 게임은 대칭 전략이 가능한 게임이다. n과 m이 모두 홀수라면, 선공은 첫 턴에 가운데의 1×1칸을 먹은 다음에, 다음턴부터는 상대가 먹는 직사각형의 점대칭 위치의 직사각형을 계속 먹는 것이 가능하다. 이것을 반복하면 결국 먹을 곳이 없어지는 것은 상대가 되므로, 선공이 항상 승리할수 있다.
  • n과 m이 홀수가 아닐때에도 대칭전략을 구사할수 있다. n과 m중 하나만 짝수라면, 첫턴에 가운데의 2×1칸을 먹으면 된다. 즉 이경우는 s가 2이상이면 선공필승이다. n과 m이 모두 짝수이면 첫턴에 가운데의 2×2칸을 먹어야 한다. 이 경우는 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()

토론

댓글을 입력하세요:
S J W Y J
 
ps/problems/boj/28754.txt · 마지막으로 수정됨: 2024/04/16 15:02 저자 teferi