====== Game of Names ======

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


++++ 처음 풀었던 (좀더 복잡하게 푸는) 풀이 |
  * [[ps:tutorial: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가 이긴다.
++++

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_3}}