[G4] 백준 12970 - AB (Python3)

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

---

풀이 아이디어

문자열의 길이에 따라 A와 B로 만들 수 있는 조합의 최대 개수가 정해져있다. 직접 여러 길이의 문자열을 만들어가며 풀이할 때 알게 된 특징이다.

길이가 10인 문자열로 만들 수 있는 조합의 최대 개수는 AAAAABBBBB로, 5*5=25개이다.

길이가 11인 문자열로 만들 수 있는 조합의 최대 개수는 AAAAAABBBBB → 5*6=30 or AAAAABBBBBB → 6*5=30

길이가 30인 문자열로 만들 수 있는 조합의 최대 개수는 15A15B → 15*15=225최대 개수의 공식은 $ \lfloor\frac{N^2}{4}\rfloor $ 이다.

 

그렇다면 최소 개수는 몇 개일까? 당연히 0개이다. 모든 길이에 대해서 A 혹은 B 문자 하나로만 나열한다면, 그 값은 0이 된다.

혹은 BBBBBAAA처럼 모든 B가 A보다 앞에 나열되어 있다면, 이 경우도 값은 0이다. 하지만 이런 경우를 따지기엔 더 쉬운 경우가 있다. 그래서 내가 문제를 풀 때는 고려하지 않았다.

 

나는 문자열에서 AB의 나열을 적절히 하면 0부터 최대 개수 사이의 모든 수를 표현할 수 있음을 알았다.

길이가 5인 문자열을 보자. →$ \lfloor\frac{5^2}{4}\rfloor $ 이므로 최대 개수는 6개이다.

AAAAA → 0

BAAAA → 0

ABAAA → 1

AABAA → 2

AAABA → 3

..

ABAAB → 2*1 + 1*2 = 4

AABAB → 2*2 + 1*1 = 5

AAABB → 2*3 = 6 

이렇게 0부터 조합의 최대 개수 까지 모든 수를 찾을 수 있다.

 

이 문제는 주어진 숫자를 만들 수 있는 아무 AB문자열을 출력해야 하므로, 0부터 순서대로 AB문자열을 만들고 검사하는 방식으로 문제를 해결하려고 했다. 부르트포스인 셈이다.

풀이👀

1. 'A'와 'B'의 최대 조합의 수를 계산하기 위해 get_max_spares(n)를 정의한다.
2. 0부터 최대 개수까지 모두 찾는 비효율적인 경우를 대비하기 위해 get_start(n, target)를 정의합니다. 이 함수는 주어진 조건을 만족하는 문자열의 최대 시작 위치를 찾는다.
   (예를 들어 10 12 가 입력으로 들어온 경우, AAAAAAAAAA(0) 보다 AAAAAAAAAB(9) 부터 찾기 시작하는 것이 목표한 12를 더 빨리 찾을 수 있을 것이다.)
3. 문자열 내에서 'A'와 'B'의 이웃한 조합 수를 계산하기 위해 get_spares(string)를 정의합니다.
4. 주어진 입력 값으로부터 조건을 만족하는 문자열을 생성합니다. 먼저, 최대 가능한 조합 수를 확인하고, 조건을 만족하는 시작 위치를 찾는다. 그 후, 문자열을 생성하고, 조건을 만족할 때까지 문자열을 변경한다.
5. 주어진 문자열에서 'B'의 위치를 이동시켜 조건을 만족하는 문자열을 생성하기 위해 change(string, idx)를 정의한다.

---

코드🐱‍👓

def get_max_spares(n):
    return int(n**2 / 4)

def get_start(n, target):
    for i in range((n+1)//2):
        if i*(n-i) <= target and target <= (i+1)*(n-i-1):
            return i

def get_spares(string):
    cnt = 0
    for i in range(len(string)):
        if string[i] == 'B':
            continue
        for j in range(i+1, len(string)):
            if string[j] == 'A':
                continue
            cnt+=1
    return cnt

def change(string, idx):
    if idx+1 < len(string) and string[idx] == 'B' and string[idx+1] == 'A':
        string[idx], string[idx+1] = string[idx+1], string[idx]
        return idx+1
    string[0] = 'B'
    return 0
        

n, k = map(int, input().split())
if get_max_spares(n) < k:
    print(-1)
else:
    tmp1 = get_start(n, k)
    string = ['A']*(n-tmp1) + ['B']*tmp1
    idx = 0
    while get_spares(string) != k:
        idx = change(string, idx)

    print(*string, sep = '')