[AtCoder] C - Robot Takahashi

https://atcoder.jp/contests/abc257/tasks/abc257_c

C - Robot Takahashi

1. 이분 탐색

2. 완전 탐색

3. 누적합

 

주의 사항

- 모든 요소가 child or adult일 가능성

- 중복된 weight 존재 가능성

 

처음에는 보자마자 이분 탐색으로 풀면 될 거 같아서 계속 도전했으나 잘되지 않았다.

이분 탐색을 하려면 답의 탐색 기준이 명확해야 했기 때문이다. 하지만 이 문제는 명확할 수 없었다.

이 문제가 요구하는 바는 단순히 child를 최대화하거나, adult를 최대화하는 것이 아니라 기존에 정해진 child / adult 여부를 최대한 맞추는 것이기 때문이다. 따라서 하나의 요소만 보고 X의 값을 정할 수가 없었다.

 

그 다음 택한 방식은 방법을 찾다찾다 완전탐색을 시도해보았다.

X가 실수의 범위이더라도 어차피 몸무게는 정수로 주어지므로, 주어진 몸무게들을 하나씩 X로 삼아서 최대화하는 방법을 찾는 단순 무식한 방법이었다. 시간복잡도는 $O(N^2)$이었고 N의 범위가 상당하다는 점에서 당연하게도 시간 초과가 발생했다.

 

그래도 무의미한 시도는 아니었다. 완전탐색을 해보면서 방법을 하나 찾아냈기 때문이다.

위의 시도들을 통해서 어떤 부분을 효율적으로 만들어야 하는지 파악할 수 있었다. 하나의 기준을 정하면 매번 모든 사람은 예상 어른 여부와 몸무게로 인해 판단된 어른 여부가 매치하는지를 확인해야한다는 점이 어려웠다.

그래서 어떻게 하면 반복적으로 매치를 확인하는 과정을 줄일 수 있을지 방법을 고민했다가 누적합을 떠올렸다.

 

우선 사람의 위치(인덱스)는 답을 구하는 데에 전혀 영향이 없다. 따라서 사람들의 예상 어른 여부만 제대로 알려준다면 몸무게 오름차순으로 정렬해도 문제가 없다. 그리고 누적합을 통해 몸무게 오름차순으로 각각 child, adult의 예상을 기록해준다.

이렇게 되면 만약 X보다 몸무게가 작은 사람들은 무조건 child, 크거나 같은 사람들은 무조건 adult라는 점이 확실하면서 한 번에 매치된 수를 일괄적으로 파악할 수 있게 된다!! 🤡

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    vector<pair<int, int>> ppl(n);
    for(int i = 0;i < n;i++) {
        int w;
        cin >> w;
        ppl[i] = make_pair(w, s[i] - '0');
    }
    sort(ppl.begin(), ppl.end());
    vector<vector<int>> prefix_sum(n, vector<int>(2, 0));
    
    if(ppl[0].second == 0) {
        prefix_sum[0][0] = 1;
    }
    else {
        prefix_sum[0][1] = 1;
    }
    
    for(int i = 1;i < n;i++) {
        if(ppl[i].second == 0) {
            prefix_sum[i][0] += prefix_sum[i - 1][0] + 1;
            prefix_sum[i][1] += prefix_sum[i - 1][1];
        }
        else {
            prefix_sum[i][0] += prefix_sum[i - 1][0];
            prefix_sum[i][1] += prefix_sum[i - 1][1] + 1;
        }
    }
    int answer = 0;
    for(int i = 0 ;i < n;i++) {
        // i번이 child인 경우
        if(i + 1 < n && ppl[i].first != ppl[i + 1].first){
            int cnt = prefix_sum[i][0] + prefix_sum[n - 1][1] - prefix_sum[i][1];
            answer = max(answer, cnt);
        }
        else if(i == n - 1) {
            int cnt = prefix_sum[i][0];
            answer = max(answer, cnt);
        }
        // i번이 adult인 경우
        if(i > 0 && ppl[i].first != ppl[i - 1].first) {
            int cnt = prefix_sum[i - 1][0] + prefix_sum[n - 1][1] - prefix_sum[i - 1][1];
            answer = max(answer, cnt);
        }
        else if(i == 0) {
            int cnt = prefix_sum[n - 1][1];
            answer = max(answer, cnt);
        }
    }
    
    cout << answer << '\n';
}