[BOJ] 12970 : AB C++

문제

정수 N과 K가 주어졌을 때, 다음 두 조건을 만족하는 문자열 S를 찾는 프로그램을 작성하시오.

• 문자열 S의 길이는 N이고, 'A', 'B'로 이루어져 있다.
• 문자열 S에는 0 ≤ i < j < N 이면서 s[i] == 'A' && s[j] == 'B'를 만족하는 (i, j) 쌍이 K개가 있다.

 

입력

첫째 줄에 N과 K가 주어진다. (2 ≤ N ≤ 50, 0 ≤ K ≤ N(N-1)/2)

 

출력

첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다.

 

예제 입력 1	예제 출력 1
3 2	ABB

예제 입력 2	예제 출력 2
2 0	BA

예제 입력 3	예제 출력 3
5 8	-1

예제 입력 4	예제 출력 4
10 12	BAABBABAAB

 

CODE

#include <bits/stdc++.h>

using namespace std;

void solve(int N, int K)
{
    if(K > (N / 2) * (N / 2 + N % 2)) // 문자열을 만들 수 없는 경우
    {
        cout << -1;
    }
    else if(K == 0) // B*A* 의 상태로 출력
    {
        for(int i = 0; i < N - 1; i++)
            cout << 'B';
        cout << 'A';
    }
    else // B를 N개 만든 뒤, 앞에서부터 차례로 A가 들어갈 수 있는 경우 A로 바꿈
    {
        for(int i = 0, j = 1, sum = 0; i < N; i++)
        {
            if(N - j - i > 0 && sum + N - j - i <= K)
            {    
                cout << 'A';
                sum += N - j++ - i;
            }
            else
                cout << 'B';
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    cin >> N >> K;
    solve(N, K);
}

 

COMMENT

1. 문자열을 만들 수 없는 경우

 - A를 a개, B를 b개 사용하여 문자열을 만든다고 가정하자. K는 문자열이 A*B* 꼴일 때 최댓값을 가지며 값은 ab이다.

 - 이 때,  a+b=N 이므로 ab의 최댓값은 a(N-a)의 최댓값과 같으며, a=N/2일 때 최댓값을 가진다. 

 - 따라서 a=N/2, b=N/2일 때의 값보다 입력받은 K값이 크면 문자열을 만들 수 없다. 

 

2. K의 값이 0인 경우

 - B*A* 꼴의 문자열일 경우 K의 값은 0이 된다.

 

3. 문자열을 만들 수 있는 경우

  1에서 K의 값이 0이상 ab이하인 모든 문자열을 만들 수 있다는 것을 증명했으므로, B가 N개인 문자열을 만들어 놓고 앞에서부터 A로 바꾸어보며 K와 비교해보면 된다.

 - i를 문자열의 index, j를 이제까지 사용한 A의 개수 + 1, K까지 도달하고자 하는 값을 sum이라고 하자.

 - 차례로 A를 넣는다면 sum의 값은 N-i-j가 증가할 것이므로, sum+N-i-j의 값이 K이하일 경우 계속해서 A를 넣어주자.

 

도움이 되셨다면 공감 꾸욱! 부탁드립니다 ~~!!😊