Game of Names

ps
링크	acmicpc.net/…
출처	BOJ
문제 번호	35127
문제명	Game of Names
레벨	플래티넘 3
분류	게임이론
시간복잡도	O(∑n)
인풋사이즈	∑n <= 2*10^5
사용한 언어	Python 3.13
제출기록	32412KB / 224ms
최고기록	224ms
해결날짜	2026/01/17

풀이

열심히 풀고 풀이도 써놨는데, 다 쓰고서 공식 풀이를 보니까 단순한 관찰을 추가해서 훨씬 간단하게 푸는 방법이 있었다.
원래 적어놨던 풀이와 코드는 망글이 되었지만, 지우지는 않고 그냥 접어놓기만 하겠다
핵심 관찰은 게임이 종료된 최종 보드에서는 이름이 abab.. 처럼 번갈아가면서 적혀지게 된다는 것. 그러므로 현재 적혀져있는 이름들의 개수와, 양 끝에 같은 이름을 적을수 있는지 여부만 확인하면 승패를 알수 있다는 것이다. 자세히는 공식 풀이 참고. 시간복잡도는 O(n)

처음 풀었던 (좀더 복잡하게 푸는) 풀이

cold game의 개념으로 보는 것이 쉽다
주어진 보드를, 연속된 빈칸들로 이루어진 구간들로 나누어서 생각하자. 각 구간들은 독립적이고, 각 구간에서의 유리도를 더한 값이 양수면 선공, 0이나 음수면 후공이 이긴다.
각 구간들의 유리도는 구간의 양끝에 있는 이름에 따라서 계산이 달라진다
- 양 끝에 다른 이름이 붙어있는 경우 (a….b 와 같은 경우)
  - 이 경우에는 누가 먼저 하든 어떻게 하든, 같은 수의 a와 b를 놓을 수 있다. 몇번 해보면 쉽게 알수 있으므로 엄밀한 증명은 생략
- 양 끝에 같은 이름이 붙어있는 경우 (a…..a 와 같은 경우)
  - 양 끝에 a가 붙어있으면, 누가 먼저 하든 어떻게 하든, b를 a보다 한개 더 많이 놓을수 있다. 양끝이 b면, a를 한개 더 많이 놓을수 있다. 유리도로 치면 양끝이 a면 -1, 양끝이 b면 +1
    - b가 먼저 하나를 채우면, 남은 구간들이 a..b와 b..a 로 나뉘어지므로, 남은 구간에서는 동일한 갯수를 채우게 되므로 결과적으로 b가 하나 더 많이 채울 수 있다
    - a가 먼저 하나를 채우면, 남을 구간들이 a…a 두개가 된다. 결국 b가 하나 더 많이 채울수 있는 구간 두개가 생기므로 결과적으로는 b 가 하나 더 많이 채을수 있다.
- 한쪽 끝이 비어있는 경우 (…a 와 같은 경우. 왼쪽 끝구간 또는 오른쪽 끝구간에만 존재)
  - 구간의 크기에 따라서 달라진다.
    - 놓을수 있는 칸이 1칸이면, 결과는 일정하다. .a 이면 b만 한번 채울수 있고, .b 이면 한번 채울수 있다
    - 구간의 크기가 2 이상이면, 이 경우는 누가 먼저 하느냐에 따라 결과가 달라진다.
      - ….a 일 경우, a가 먼저 하면 양쪽이 동일한 개수를 채울수 있다. b가 먼저 하면 b가 한개 더 많이 채울수 있다.
      - 이렇게 한쪽이 비어있고, 구간의 크기가 2 이상인 구간을 끝구간이라고 부르자.
결국 기본 전략은, 먼저 하는 플레이어가 우위를 가져올수 있는 끝구간을 먼저 채우고, 그 다음은 그냥 아무렇게나 채우는 것이다. 유리도 계산은, 끝 구간에서 얻을수 있는 유리도 + 나머지 구간에서 얻을수 있는 유리도로 계산한다
끝구간에서 얻을수 있는 유리도 계산은
- 끝 구간이 0개이면 +0
- 끝 구간이 1개이고 …a 이면, a가 먼저 채워서 상대가 이득보는것을 막으니까 +0
- 끝 구간이 1개이고 …b 이면, a가 먼저 채워서 이득을 보니까 +1
- 끝 구간이 2개이고 …a, …a 이면, a가 하나를 지켜도, 다른쪽에서 b가 이득을 보므로 -1
- 끝 구간이 2개이고 …b, …b 이면, a가 하나에서 이득보고, 다른쪽을 b가 지키므로 +1
- 끝 구간이 2개이고 …a, …b 이면, 서로 하나씩 지켜서 +0
이제 여기에 나머지 구간에서의 유리도를 모두 더해서, 0보다 큰지 확인하면 끝. 시간복잡도는 O(n)
위에서 체크하지 않은 케이스가 하나 있다
- 이미 적혀져있는 이름이 하나도 없는 경우이다. 이때는 양끝이 모두 비어있는 구간 1개가 나오고, 이경우의 유리도는 0이므로 b가 이긴다는 것을 쉽게 찾을수 있다. 하지만, 여기에서도 다시 n=1 일때의 예외처리를 해줘야 한다. n이 1일 경우에는 a가 이긴다.

코드

"""Solution code for "BOJ 35127. Game of Names".

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

Tags: [game theory]
"""

import sys
from teflib import psutils


@psutils.run_n_times
def main():
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().rstrip()

    if s.count('.') == n:
        print('bob' if n > 1 else 'alice')
        return

    left, right = None, None
    if s[0] != '.':
        left = s[0]
    elif s[1] != '.':
        left = 'a' if s[1] == 'b' else 'b'
    if s[-1] != '.':
        right = s[-1]
    elif s[-2] != '.':
        right = 'a' if s[-2] == 'b' else 'b'

    if left is None and right is None:
        left, right = 'a', 'b'
    elif left is None:
        left = 'a'
    elif right is None:
        right = 'a'

    adv = s.count('b') - s.count('a')
    if left == right:
        adv += 1 if left == 'a' else -1

    print('alice' if adv > 0 else 'bob')


if __name__ == '__main__':
    main()

BOJ, 플래티넘 3

목차

Game of Names

풀이

코드