[백준] 원숭이 스포츠

https://www.acmicpc.net/problem/16438

16438번: 원숭이 스포츠

문제를 제대로 이해하지 못해서 조금 헤맸던 문제입니다. 이 문제의 포인트는 분할정복입니다. 절반으로 쪼개면서 현재 범위에서의 절반과 나머지 절반이 상대팀이 되도록 하면 됩니다. 예를 들어 n = 7일때, AAABBBB -> ABBAABB -> AABABAB순으로 팀을 나누어 주면 최소 한번은 다른 원숭이들과 상대팀이 될 수 있습니다. 7개의 팀 조합을 출력해야하므로 나머지 4개의 조합은 아무렇게나 출력해주면 됩니다.

 

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

cur = ['A'] * n

check = [
    [False] * n
    for _ in range(n)
]

ans = set()

def dq():
    q = deque([(0, n)])

    # 계속해서 반으로 쪼개면서 서로 상대팀이 되도록 한다.
    while q:
        for _ in range(len(q)):
            start, end = q.popleft()

            if end - start <= 1:
                continue

            mid = (start + end) // 2

            for i in range(start, mid):
                cur[i] = 'A'

            for i in range(mid, end):
                cur[i] = 'B'
            q.append((start, mid))
            q.append((mid, end))

        ans.add(''.join(cur))

dq()


for a in ans:
    print(a)

for _ in range(7 - len(ans)):
    print('A' + ('B' * (n - 1)))