[백준/C++/KOI] 25381번 ABBC

---

문제를 처음 읽었을 때 그냥 그리디하게 풀면 되지 않나? 라는 생각이 들어 제한조건을 보니 S < 300000이었다. 2가지 지우는 방법을 모두 실행한다고 가정하여도 2 * 300000 이라 시간제한이 너무 널널해 잘못된 풀이인가? 하고 고민했다.

 

3초면 n logn 풀이가 있는 것인가 하고 고민하였는데 아무리 생각해도 그리디로 풀릴 것 같아서 편하게 짠 첫 코드는 5점을 맞았다.

 

처음 짠 코드는 2번 예제에 문제점을 해결할 수 있도록 뒤에서부터 C의 갯수를 세고 C의 앞에 B가 있다면 지워주는 방식을 생각했다.

지운 B의 위치를 bool로 체크해준 후 A를 세고 A의 앞에 B가 있다면 지우는 형식으로 짰었다.

 

틀린 이유를 고민하다가 발견한 반례는 BABC였다 CB를 먼저 지우면 A가 혼자 떨어지기 때문에 AB를 세고 BC를 세야하나? 고민하던 찰나 ABCB로 나오면 역시 해결할 수 없다는 것을 발견하였다.

 

그렇다면 내가 무엇을 그리디하게 가져가야하는가를 다시 생각해보았고 결국 모든 B를 지우는게 최종 목적이므로 내가 가진 B를 최대한 많이 앞에서부터 지울 수 있는 방법을 찾아야한다는 것으로 정리하였다.

 

증명

1. 최대 횟수는 B를 가장 많이 지우는 것이다.
2. 더 이상 AB혹은 BC로 짝을 지을 수 없을 때까지 최대한 B를 제거해야한다.
3. 앞에서부터 순서대로 B를 지워 지울 수 있는 최대 B의 갯수를 찾는다.

---

#include <iostream>
#include <queue>
using namespace std ;
bool check[300001] ;
int check_box, answer ;
string str ;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0) ;
    cin >> str ;
    queue<int> que ;

    for(int i = 0 ; i < str.length() ; i++)
    {
        if(str[i] == 'B') que.push(i) ;
        else if(str[i] == 'C' && !que.empty())
        {
            check[que.front()] = 1 ;
            que.pop() ;
            answer++ ;
        }
    }

    que = queue<int>() ; check_box = 0 ;
    for(int i = 0 ; i < str.length() ; i++)
    {
        if(str[i] == 'A') check_box++ ;
        else if(str[i] == 'B' && check_box && !check[i])
        {
            check[i] = 1 ;
            check_box-- ;
            answer ++ ;
        }
    }

    cout << answer ;
}

---

느낀점: 그리디하게 할 수 있을 것 같다면 무엇을 어떠하게 탐욕적으로 가져갈 것인가를 생각해보고 풀이를 진행해야겠다고 느꼈다.

문제링크 : https://www.acmicpc.net/problem/25381

25381번: ABBC