BOJ) 12970 - AB

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

12970번: AB

백트랙킹으로 접근했을 때, 메모리/시간 모두 간신히 통과했던 문제입니다.

 

새로운 방식의 풀이에

- A의 갯수 + B의 갯수 = 전체 문자열의 길이 N

- 만들어야 하는 쌍의 갯수 K의 범위 : 0 ~ (A의 갯수)x(B의 갯수) 

위 두 가지 성질을 이용해 그리디 기법으로 접근하여 적은 메모리와 빠른 시간에 문제를 해결할 수 있었습니다.

---

C++ 소스 코드

#include <iostream>
#include <vector>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin >> n >> k;
    for(int a=0;a<=n;a++){
        //a의 갯수 0~N개 for 문
        int b= n-a; // a+b = N
        // 가능한 쌍의 범위 : 0<= K <= a*b
        if (a*b < k) continue;
        //b의 왼쪽 끝부터 오른쪽 끝까지 
        vector<int> cnt(b+1);
        for(int i=0;i<a;i++){
            int x = min(b,k);
            cnt[x]+=1;
            // x 위치에 a를 한개 추가할 때마다 x개의 쌍이 생김
            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;
}