BOJ 12970 - AB

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

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

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

Solution

우선 문제를 이해하기위해 예시를 들어보자면

n=3, k=2 일때

ABB 라는 답이 나올 수 있다.

[0][1] 로 AB쌍을 1개 만들고, [0][2] 로 AB쌍을 1개 만들 수 있어 2개의 쌍을 만들 수 있다.

위의 예시에서 보면 2개의 쌍을 만들기위해서 2개의 B앞에 A를 배치하였다.
이와 같이 B를 기준으로 어느곳에 A를 배치하느냐에 따라 쌍의 개수를 결정할 수 있다.

BB 일시 _B_B_ -> 2 B 1 B 0

_는 A를 넣을수 있는 공간이고, A를 넣었을때 쌍이 생기는 수만큼 표시해보았다.

n이 4일시 AB쌍의 최대개수는 a=2, b=2 -> a*b = 4개가 최대이다. (AABB)


정리해보자면

1. A와 B의 개수를 정해주고 만들 수 있는 최대쌍의 개수(a*b)가 k보다 크거나 같은지 검사해주고

2. A를 어느곳에, 몇개를 위치하면 되는지를 확인해준다.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k;

    cin >> n >> k;

    for (int a = 0; a <= n; a++) { //A와 B의 개수를 정하기
        int b = n - a;
        if (a * b < k) continue; //주어진 조건의 쌍을 만들수 있는지 검사! 

        vector<int> cnt(b + 1);
        for (int i = 0; i < a; i++) { //A가 B사이에 들어갈 수 있는 횟수 ! (A의 개수)
            int x = min(b, k); //위치할곳을 찾음
            cnt[x] += 1; // 위치에 A를 추가
            k -= x; // 추가된 쌍만큼 없애준다.
        }
    
        for (int i = b; i >= 0; i--) {
            for (int j = 0; j < cnt[i]; j++) { //A가 삽입되어있으면 출력
                cout << 'A';
            }

            if (i > 0) {
                cout << 'B';
            }
        }

        cout << '\n';
        return 0;
    }

    cout << -1 << '\n';

    return 0;

}

참고 : https://code.plus/course/43 , 그리디 알고리즘(연습)