사용자 도구

사이트 도구


ps:problems:boj:30477

Blackboard Game

ps
링크acmicpc.net/…
출처BOJ
문제 번호30477
문제명Blackboard Game
레벨골드 1
분류

게임이론

시간복잡도O(n)
인풋사이즈n<=1000
사용한 언어Python 3.11
제출기록34008KB / 60ms
최고기록40ms
해결날짜2023/12/11

풀이

  • 직관적으로 후공이 이길수 있는 상황이 별로 없다.
  • 게임이 쭉 진행되어서 마지막 턴이 되었을때, 즉 수가 A,B,C 3개만 남았을때의 상황을 생각해보자. 그 이전턴까지 선공의 숫자의 합이 후공의 숫자의 합보다 큰 상황이라면, 선공은 A,B,C 중에서 가장 큰 수를 고르면 된다. 그러면 후공은 남은 두개의 수중 무엇을 고르더라도 숫자의 합이 같아지게 만들수 없다. 만약 선공의 숫자의 합이 후공의 숫자의 합보다 작다면, 선공은 A,B,C 중 가장 작은 수를 고르면 된다. 그러면, 선공이 이길수 없는 유일한 상황은 그 이전턴까지 선공의 숫자의 합이 후공의 숫자의 합과 같고, 남은 수 세개가 전부 같을 경우이다. 이경우만이 후공이 이길수 있는 유일한 경우이다
  • 그러면, 후공이 이기기 위해서는, 매턴이 끝날때마다 선공의 점수의 합과 후공의 점수의 합을 동일하게 유지해야 한다. 즉, 선공이 고른 수와 같은 수를 후공이 골라야 한다. 이러기 위해서는 모든 수가 2개 이상 있어야 한다. 또한 후공이 선공이 고른 수와 같은 수를 고르고 나서, 다른 수 한개를 지울텐데, 그러고 나서도 그 다른수도 여전히 2개 이상이 남아있어야 한다. 이것을 계속 유지하기 위해서는, 모든 수의 개수가 3의 배수로 있어야 한다. 이제 후공은 선공이 고른 수를 고르고 또 그 수를 지우는 식으로 모든 턴을 진행하는 방식으로 승리할수 있다.
  • 정리하면, 모든 수의 개수가 3의 배수이면 후공 승리, 그외에는 선공의 승리. 이것을 체크하는 시간복잡도는 O(n)

코드

"""Solution code for "BOJ 30477. Blackboard Game".

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

Tags: [game theory]
"""

import collections


def main():
    N = int(input())  # pylint: disable=unused-variable
    B = input().split()

    counter = collections.Counter(B)
    print('N' if all(x % 3 == 0 for x in counter.values()) else 'Y')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
E F R N U
 
ps/problems/boj/30477.txt · 마지막으로 수정됨: 2023/12/11 13:35 저자 teferi