백준 12970 - AB (C++)

문제

• 문제 링크

  
   BOJ 12970 - AB 
  

• 문제 요약

정수 $N$과 $K$가 주어진다.
문제에 정의된 두 조건을 만족하는 문자열 $S$를 찾아보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$2 ≤ N ≤ 50$

$0 ≤ K ≤ N(N-1)/2$

알고리즘 분류

• 수학(math)
• 그리디 알고리즘(greedy)
• 구성적(constructive)

풀이

나는 우선 $A$로만 이루어진 길이 $N$의 문자열을 시작으로 잡았다.
이후 다음 두 값을 비교해 최솟값을 찾아 문자열을 맞춰 나갔다.

• $B$가 가장 처음 등장하기 전 인덱스.(맨 처음엔 당연히 맨 끝)
• 남은 $K$와 $B$ 가 가장 처음 등장한 인덱스로부터 맨 끝까지 등장하는 '$B$'의 개수의 합

두번째 값을 저렇게 추린 이유는, 기존 $A$를 $B$로 변환함에 따라 해당 $A$ 때문에 이뤄졌던 쌍들이 사라지게 되기 때문이다.
마지막으로 $S$가 존재하지 않는 경우란 맨 처음 $A$까지 $B$로 변환 했는데 $k$가 여전히 남아 있는 경우일 것이다.

자세한 건 아래 코드를 보는 것이 이해가 빠를 듯 하다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
string s;
int n, k;
 
int main()
{
    for (cin >> n >> k; n--; s.push_back('A'));
    while (s[0] ^ 'B')
    {
        int i = find(s.begin(), s.end(), 'B') - s.begin() - 1;
        int d = min(i, k + (int)count(s.begin() + i + 1, s.end(), 'B'));
        s[d] = 'B';
        k += count(s.begin() + d, s.end(), 'B'); k -= d + 1;
        if (!k) cout << s, exit(0);
    }
    puts("-1");
}

comment

끝