[백준 12970] 그리디 AB

백준 12970

(A, B) 쌍의 개수 구하기

먼저 해당문제는 특정 문자열에서 (A, B) 쌍의 개수를 구해야한다.
예를 들어 ABBAABBB 라는 문자열에서 (A, B) 쌍의 개수를 구해봅시다.
모든 A에 대해서 각 A 뒤에 있는 B의 개수를 구해서 더하거나 모든 B에 대해서 각 B 앞에 있는 A의 개수를 구해서 더하면 된다.

첫 번째 A에 대해서 뒤에 있는 B의 개수는 5, 두 번째와 세 번째 A에 대해서 뒤에 있는 B의 개수는 3이다.

즉 5+3*2=11, (A, B) 쌍의 개수는 11개가 된다.

A와 B의 개수가 주어질 때 (A, B) 쌍이 가장 많은 문자열

그럼 (A,B) 쌍이 가장 많은 문자열을 어떻게 구할까? 쌍을 구할떄마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 어떻게 도달할까

• 최적의 상황 가정
  • 모든 A를 연속하여 붙이고 그 뒤에 모든 B를 붙이면 된다.
    예를 들어 A의 개수가 4이고 B의 개수가 5라면 (A, B) 쌍의 개수가 최대가 되는 문자열은 무조건 AAAABBBBB이다.
    A가 연속한다면 모든 B에 대해서 쌍을 생성할 수 있는데 연속하지 않다면 쌍을 생성할 수 없는 B가 생기기 때문이다.

💻 해당 문제에 알고리즘 적용

import sys

input=sys.stdin.readline

n,k =map(int, input().split())
s=['B']*n
cnt=0
max_cnt=0
for i in range(n//2+1):
    max_cnt=max(max_cnt, i*(n-i))
if max_cnt<k:
    print(-1)
    exit()

필자는 해당 연산을 선택했다
1. 문자열의 뒷 부분을 A로 바꾸고 한 칸씩 앞으로 떙겨온다.

> 2번 연산만 사용하면 모든 cnt를 탐색할 수 있다.

예시

BBBBB에서 cnt는 0이고 2번 연산을 계속 적용해보자.

문자열	cnt
BBBBB	0
BBBBA	0
BBBAB	1
BBABB	2
BABBB	3
ABBBB	4
ABBBA	3
ABBAB	4
ABABB	5
AABBB	6

보다싶이 모든 경우를 탐색할 수 있다.
그런데 만약 A의 개수가 과반수가 넘어가면 어떨까?

AAAAAAAABBBB 이러한 문자열에서 2번 연산을 계속 적용해보면 어떨까? 처음에는 cnt가 32이다.

문자열	cnt
AAAAAAAABBBB	32
AAAAAAAABBBA	24
AAAAAAAABBAB	25
AAAAAAAABABB	26
AAAAAAAAABBB	27
AAAAAAAAABBA	19

28에서 31까지 나오지 않는 모습을 볼 수 있다. 그러면 이 수에 대해서는 탐색을 못하니 모든 경우를 탐색하는게 아닐까?

그런데 모두 B로 이루어진 문자열에서 2번 연산만 계속 적용하다보면 A가 과반수가 넘어가는 일 자체가 발생하지 않는다.

A와 B의 개수가 주어질 때 (A, B) 쌍이 가장 많은 문자열을 구하는 방법을 다시 생각해보자.

길이가 8인 문자열에서 (A, B)쌍이 가장 많은 문자열은 무엇일까?

당연히 AAAABBBB 처럼 A와 B의 개수가 가장 비슷한 문자열이다.

AAAAABBB 처럼 A의 개수가 과반수가 넘어가는 순간 (A, B) 쌍의 개수가 줄어든다.(애초에 고려할 필요가 없다!)

즉 A의 개수가 과반수가 되기 전까지는 완전 탐색이 맞고 A의 개수가 과반수가 될 때까지 cnt가 k가 되지 못했다면 애초에 만들 수 없는 문자열일테고 가장 처음에 만들 수 없는 문자열은 걸러냈기 때문에 이러한 상황 자체가 발생하지 않는다.

👉 최종 코드

import sys

input=sys.stdin.readline

n,k =map(int, input().split())
s=['B']*n
cnt=0
max_cnt=0
for i in range(n//2+1):
    max_cnt=max(max_cnt, i*(n-i))
if max_cnt<k:
    print(-1)
    exit()
while cnt!=k:
    idx=n-1
    cnt-=s.count('A')
    s[idx]='A'
    while idx>0 and s[idx-1]=='B' and cnt!=k:
        s[idx]='B'
        idx-=1
        s[idx]='A'
        cnt+=1
print(''.join(s))