[Python] 백준 12970번: AB

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

12970번: AB

 

import sys
input = sys.stdin.readline


def getStr(N, K):
    curStr = ['B']*N
    aCount = 0
    curK = 0
    lastAIndex = -1

    while curK < K:
        if lastAIndex <= aCount-1:
            if curStr[N-1-(aCount+1)] == 'A':
                break
            else:
                curStr[N-1-(aCount+1)] = 'A'
                lastAIndex = N-1-(aCount+1)
                aCount += 1
                curK += 1
        else:
            curStr[lastAIndex] = 'B'
            curStr[lastAIndex-1] = 'A'
            lastAIndex -= 1
            curK += 1

    if curK == K:
        return curStr
    else:
        return "-1"


N, K = map(int, input().split())
print("".join(getStr(N, K)))

 

패턴부터 파악해야한다. 문자열 길이가 6이라고 했을 때 K가 0일 때부터 시작해서 살펴보자.

 

BBBBBB

BBBBAB

BBBABB

BBABBB

BABBBB

ABBBBB

 

우선 아직까진 패턴이 쉽다. 그럼 다음엔 어떻게 해야할까? A를 하나를 더 추가를 해야하는데, 그 위치가 고민이다. ABBBBB에서 A가 B에 대한 5개의 쌍을 이루는데, A를 넣게 되면 4쌍으로 바뀐다. 즉 K가 -1이 추가되므로, 새로운 A가 2개의 쌍을 이루도록 넣으면 된다. 그러므로 다음 문자열은 ABBABB이 된다. 이후에는 처음에 본 패턴과 같이, ABABBB -> AABBBB 순서로 흘러간다.

그러면 문자열이 변화할 때 2가지의 패턴을 가진다. 첫째는 A를 앞으로 밀어내는 식, 두번째는 A를 하나 추가하는 것이다. 이제 후자의 패턴을 분석해보자.

AABBBB의 다음 문자열은 무엇인가? ABBBBB의 경우와 같이 생각해보면 AAABBB이다. 왜냐하면 2개의 A가 각 4개의 쌍을 이루고 있으며, 여기에 A를 추가하면 각 3개의 쌍을 이루게 되어 총 2개가 사라지므로, 추가된 A는 3개의 쌍을 이루어야 하기 때문이다.

 

그럼 이것을 바탕으로 코드를 짜보자. 우선 while문을 돌면서 curK 값을 K에 도달하게끔, curStr을 계속해서 변형시키는 게 큰 틀이다. 그 안은 크게 2개의 분기점으로 나뉘는데, 이는 앞서 설명한 2개의 패턴이다. 전자가 A를 추가하는 경우, 후자가 A를 앞으로 미는 경우이다. A를 추가하는 인덱스(N-1-(aCount+1))에 이미 A가 있다면 N개의 문자로 K라는 값에 도달하지 못한다는 의미이므로, break문을 수행한다.