BOJ 32027 : 미어캣

• 문제 링크 : boj.kr/32027
• 난이도 : P4
• 태그 : 그리디, 정렬, 브루트포스

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<bool> place(n); // LR
    vector<int> L, R;
    for(int i = 0; i < n; i++) {
        int a;
        string s;
        cin >> a >> s;
        if(s == "R") {
            R.emplace_back(a);
            place[i] = 1;
        }
        else {
            L.emplace_back(a);
            place[i] = 0;
        }
    }
    sort(all(R));
    sort(all(L));

    int M;
    bool Md;
    if(R.size() == 0) {
        M = L.back();
        Md = 0;
        L.pop_back();
    } 
    else if(L.size() == 0) {
        M = R.back();
        Md = 1;
        R.pop_back();
    }
    else {
        if(R.back() < L.back()) {
            M = L.back();
            Md = 0;
            L.pop_back();
        }
        else {
            M = R.back();
            Md = 1;
            R.pop_back();
        }
    }

    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(place[i] != Md) continue;
        vector<int> temp(n);
        temp[i] = M;

        int ridx = 0;
        for(int j = 0; j < i; j++) {
            if(place[j] == 1) {
                temp[j] = R[ridx];
                ridx++;
            }
        }
        int lidx = 0;
        for(int j = n-1; j > i; j--) {
            if(place[j] == 0) {
                temp[j] = L[lidx];
                lidx++;
            }
        }

        int cnt = 1;
        int LM = 0;
        for(int j = 0; j < i; j++) {
            if(place[j] == 0) {
                while(lidx < L.size() && L[lidx] <= LM) {
                    lidx++;
                }
                if(lidx < L.size()) {
                    cnt++;
                    temp[j] = L[lidx];
                }
            }
            LM = max(LM, temp[j]);
        }
        int RM = 0;
        for(int j = n-1; j > i; j--) {
            if(place[j] == 1) {
                while(ridx < R.size() && R[ridx] <= RM) {
                    ridx++;
                }
                if(ridx < R.size()) {
                    cnt++;
                    temp[j] = R[ridx];
                }
            }
            RM = max(RM, temp[j]);
        }
        ans = max(ans, cnt);
    }
    cout << ans;

    return 0;
}

---

풀이

키가 제일 큰 미어캣을 기준으로 생각해보자.

이 미어캣을 기준으로 왼쪽에 있는 R미어캣은 절대 망을 볼 수 없다.

반대의 경우도 마찬가지이다.

 

절대 망을 볼 수 없는 곳에 필요 없는 미어캣을 버려야 한다.

기준에서 먼 곳부터 작은 미어캣을 배치한다.

이후에 기준의 왼쪽에는 왼쪽을 보는 미어캣을 망을 볼 수 있는 가장 작은 미어캣이 오도록 배치한다. 오른쪽의 경우도 마찬가지로 할 수 있다.