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()
ps/problems/boj/28754.txt · 마지막으로 수정됨: 2024/04/16 15:02 저자 teferi
토론