사용자 도구

사이트 도구


ps:problems:boj:8055

Polygons

ps
링크acmicpc.net/…
출처BOJ
문제 번호8055
문제명Polygons
레벨실버 3
분류

게임이론

시간복잡도O(1)
사용한 언어Python 3.11
제출기록31120KB / 40ms
최고기록40ms
해결날짜2023/12/15

풀이

  • 다각형에서 삼각형들을 지워나가다가, 검정색 삼각형의 세 변중 두 변이 다각형의 변이 되는 순간, 검정색 삼각형을 제거할수 있게 된다.
  • 따라서 두 플레이어는 모두 검정색 삼각형의 두 변이 다각형의 변이 되지 않도록 삼각형을 지워야 한다. 이것이 불가능해지면 지게된다.
  • 다시 말하면, 검정색 삼각형과 변을 공유하는 삼각형이 최대 세개가 있을텐데, 이 삼각형이 1개만 남으면 진다. 그래서 둘다 이 삼각형들을 제외한 다른 삼각형들을 지우려고 할것이고, 이렇게 지우다보면 최후에는 검정 삼각형을 사이에 두고 하얀 삼각형 두개가 붙어있는 5각형 모양이 남게 된다. 여기에서 하얀 삼각형을 지우면 상대 플레이어가 검정 삼각형을 지울수 있게 되어 상대가 이긴다.
  • 이렇게 되는 턴이 누구에세 돌아오느냐 하는 것은, n이 홀수인지 짝수인지만 확인하면 된다. n이 짝수면 선공 승, n이 홀수면 후공 승. 처음에 대각선들이 어떤식으로 그어져있는지는 상관 없다. 입력을 다 읽을 필요도 없어서 시간복잡도는 O(1)
  • 한가지 예외는, 첫턴에 바로 검정 삼각형을 지울수 있는 형태로 주어지는 것. 검정 삼각형의 세 변중 2개의 변이 n각형의 변에 해당한다면, n의 홀짝과 관계없이 선공의 승리이다.

코드

"""Solution code for "BOJ 8055. Polygons".

- Problem link: https://www.acmicpc.net/problem/8055
- Solution link: http://www.teferi.net/ps/problems/boj/8055

Tags: [game theory]
"""

import sys


def is_outer_edge(x, y, n):
    return abs(x - y) in (1, n - 1)


def main():
    n = int(sys.stdin.readline())
    a, b, c = [int(x) for x in sys.stdin.readline().split()]
    if (
        sum(1 for x, y in ((a, b), (b, c), (c, a)) if is_outer_edge(x, y, n))
        == 2
    ):
        print('TAK')
    else:
        print('TAK' if n % 2 == 0 else 'NIE')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
W T S D E
 
ps/problems/boj/8055.txt · 마지막으로 수정됨: 2023/12/15 05:58 저자 teferi