백준 12970번 AB[C++]

1. 문제 풀이

 문제 유형은 그리디입니다. 코드포스에서 나올법한 문제였습니다. 

 

정수 N, K에 대해서 임의의 문자열 S는 다음과 같은 조건을 만족합니다.

• 문자열 S의 길이는 N이고, 'A' 또는 'B' 문자로만 이루어져 있다.
• 문자열 S는 0 <= i < j < N을 만족하는 정수 i, j에 대해서 S[i] == 'A' && S[j] == 'B'를 만족하는 ( i, j ) 쌍이 K개 존재한다.

---

1. N, K를 입력받은 다음, 'B'로만 이루어진 길이 N의 문자열을 선언합니다.
2. 루프를 돌면서 현재 위치 idx에 대해서 S[idx]를 A로 바꾸었을 때, 두 번째 조건을 만족하는 쌍이 몇 개 나오는지 검사합니다. 
   1. 여기서 [ 0, idx ) 구간에서 'A'로 바꾼 횟수를 세어야 합니다.
   2.  S[idx] 문자를 'B'에서 'A'로 바꾸게 된다면 이전에 계산했었던 쌍의 개수가 변동되기 때문
   3. AABBB는 2 번째 조건을 만족하는 ( i , j ) 쌍이 6개 존재합니다. 여기서 AABAB로 바꾼다면 쌍의 개수가 7개가 아닌 5개로 바뀌게 됩니다
3. 문자열의 끝까지 돌았거나 도중 K가 0이 되었다면 루프를 종료하고, K가 0이 아니라면 -1을 0이라면 해당 문자열을 출력

 

2. 소요 시간 및 경과

• 시작 시간: 14시 40분
• #1 제출 시간: 14시 53분
  • AC

총 소요 시간: 13분

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, k;
string ans;

int main() {
    fastio(nullptr, false);
    
    cin >> n >> k;
    ans = string(n, 'B');
    
    int cntA{};
    for(int idx = 0; idx < n; idx++) {
        int cntB = n - idx - 1;
        if(k >= cntB - cntA) {
            k -= cntB - cntA;
            ans[idx] = 'A';
            cntA++;
        }
        
        if(!k) break;
    }

    cout << (k ? "-1" : ans);
}

.

 시간복잡도: O(N)

4. 제출 결과