[Greedy] 백준 25381, ABBC

 

 이 문제의 해결 전략을 뭘까? 맨 처음 의심한 것은 A, B, C 3개중 한개로 입력이 좁혀져서 DP로 푸는 문제라고 생각했으나S의 길이가 30만에 육박한다. dp로 풀기에는 좀 크기가 큰 편이다. 그럼 어떻게? 이 문제는 Greedy 문제로, 핵심관찰이 중요한 문제다. Greedy는 규칙을 발견하면 정말 쉽게 풀 수 있지만, 규칙을 발견하지 못하면 손도 대지 못하는 양날의 검같은 문제가 많다. 그나저나 무엇이 핵심 관찰일까? 

 1) A, B를 지우거나 B, C를 지우거나 공통적으로 B를 포함하고 있다는 점이다. B의 갯수가 중요하다. 

 2) 문자열 S에서 A, B를 만들수 있는데 B, C 때문에 못만드는 경우는 어떤 경우일까? A, B에서 B를 B, C로 만드는데 사용하는 경우다. 그렇다면 A, B를 만들거나 B, C를 만들수 있다면 적어도 하나는 만들수 있다는 뜻이다. 

 3) 좀더 생각해 보면 S열을 돌아보면서 A, B를 만들 수 있는 case를 모두 구하고, B, C를 만들 수 있는 모든 경우를 구해 놓고 그 합만큰 만들 수 있는 경우는? 순서와는 상관없이 B가 충분히 많은 경우다. 순서는 이미 A, B와 B, C를 만드는 경우에서 모두 고려되었다. 그럼 반대로 생각해서 다 못만드는 경우는? B가 충분히 없는 경우다. 

 결론적으로 다음의 식을 만족해야 한다. 

 

$$ ans = min(AB 생성가능 갯수 + BC 생성가능 갯수, B의 갯수) $$

 

 그렇다면 문제는 정말 심플해 진다. 문장 S를 순회하면서 AB 생성 갯수, BC 생성 갯수, B의 갯수를 세기만 하면 된다. 그런데 AB 생성 갯수를 구하는데 실수하기 쉬운 부분이 있다. 가볍게 생각하면 'A'가 나왔을 때 'B'가 나올때까지 index를 전진하면서 갯수를 세면 될 것 같지만, "AAABBB"  와 같은 경우에는 문제가 발생할 수 있다. 그렇다면? A의 갯수를 누적시키면서 전진하면서 B가 나오면 counting을 해주면서 A의 갯수를 하나 줄이는 식으로 접근해야 한다. 아래 코드를 보면 이해가 쉬울 것이다.  

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)

using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vb = vector<bool>;

string s;
void solve() {
    cin >> s;
    int sz = size(s);
    int ans_t = 0;
    int cnt_a = 0, cnt_b = 0, cnt_bb = 0;
    for(int i=0; i<sz; ++i) {
        if(s[i]=='A') ++cnt_a;
        if(s[i]=='B' && cnt_a) {
            ++ans_t;
            --cnt_a;
        }
    }
    for(int i=0;i<sz;++i) {
        if(s[i]=='B') ++cnt_b;
        if(s[i]=='C' && cnt_b) {
            ++ans_t;
            --cnt_b;
        }
    }
    for(int i=0; i<sz;++i) {
        if(s[i]=='B') ++cnt_bb;
    }
    int ans = min(cnt_bb, ans_t);
    cout << ans << '\n';
}

int main() {
    fastio;
    solve();
    return 0;
}