BOJ 13333, Q-인덱스

@markdown

ACM-ICPC 2016년 대한민국 인터넷 예선에 출제되었던 문제입니다. 

Q-Index라는 개념을 이용해 문제를 푸는 것이었는데요.

번역문보다 원문을 보는게 이해가 빠른 문제라 푸는데 조금 시간이 걸렸던 문제입니다.

문제를 해설해보면

"Q 인덱스가 k이다" 라는 말은 

 " n개중에 k개의 논문이 k번 이상 인용되었고

   n-k의 논문이 k번 미만 인용되었다."

라는 의미입니다.

논문의 개수와 인용회수의 범위를 살펴보면,

논문의 개수 n은 1 이상 1000이하,

논문의 인용 회수(편의상 m)은 0이상 10000이하 라고 되어있습니다.

제가 생각하는 간단한 문제 풀이 방법은, 논문의 인용 횟수를 통해, 존재하는 논문을 전부 탐색해서, q-index의 최대값을 구하는 방법입니다.

Psuedo Code를 작성해보자면

```

for( i : paper1 ~ paper n){

    for( k : cited = 0 ~ cited = 10000){

        if( 인용회수of paper[i] >= k) over++;

        if( 인용회수of paper[i] < k) nonover++;

    }

    if(over >= k && nonover <= n-k){

        q = max(q,k);

    }

}

```

처럼 푸는 방법입니다.

위 방법처럼 문제를 해결하면 O(Nk)의 시간복잡도로 문제를 해결 할 수 있기 떄문에, 제한 시간 내로 문제를 해결할 수 있습니다.

아래는 소스코드입니다

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
 
    int n;
    vector<int> v;
    scanf("%d", &n);
    for (auto i = 0; i != n; i++) {
        int tmp; scanf("%d", &tmp);
        v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    int q = -1;
    for (auto i = 0; i != 10000 + 1; i++) {
        int over = 0;
        int nonover = 0;
 
        for (auto j = v.begin(); j != v.end(); j++) {
            if (*j >= i) over++;
            else if (*j < i) {
                nonover++;
 
            }
        }
        if (over >= i && nonover <= (n - i)) {
            q = max(q,i);
        }
    }
 
    cout << q;
 
    return 0;
}