백준 21820 Acowdemia I [C]

문제

https://www.acmicpc.net/problem/21820

21820번: Acowdemia I

 

문제해설

첫째줄에는 배시가 낸 논문의 갯수 N과 논문 인용 추가횟수 L이 주어지며, 둘째줄에는 논문마다 논문의 인용횟수가 입력이 된다. 연구자를 평가하는 H-Index 라는 지표가 있는데, 논문 H개가 H번 이상의 인용횟수가 있다면 배시의 H-Index는 H가 된다. 또, 배시 자기자신이 낸 논문중 L개만큼 최대 1번만큼 인용횟수를 추가할 수 있다. 예를 들어, 인용된 횟수가 1,100,2,3 인 논문 4개가 있다고 가정해보자. 이 경우에는 2개의 논문이 2번 이상이 인용되었기 때문에 H-Index는 2가 되고, 인용된 횟수가 1,100,3,3 인 논문 4개가 있다고 가정하면, 3개의 논문이 3번 이상 인용되었기 때문에 H-Index는 3이 되는 것이다. 배시의 최대 H-Index를 찾는 것이 문제이다. 

 

풀이

인용횟수로 오름차순으로 정렬을 하면, N-i 개만큼의 논문의 이용횟수가 i 번째 논문 인용횟수보다 많음을 보장할 수 있다. (0 <= i < N)

이 때 세가지 경우로 나누어 생각해보면,

1. N-i>=i 번째 논문 이용횟수라면, i번째 논문 이용횟수로 H-Index의 조건을 만족한다.

2. N-i>=i 번째 논문 이용횟수 + 1이고 전체 논문 중 인용횟수가 i번째 논문 인용횟수와 같은 논문의 갯수가 L개 이하라면, i번째 논문 이용횟수 + 1로 H-Index의 조건을 만족한다. 

3. i 번째 논문 인용횟수 >= N-i 라면, N-i 로 H-Index의 조건을 만족한다.

전체 논문을 탐색해가며 3가지 경우중에 조건을 만족하는 가장 큰 H-Index값을 출력해주면 된다. 

 

코드

#include<stdio.h>
#include<algorithm>

#define LEN 210000
using namespace std;

int N, L, set[LEN], cnt[LEN];

int main() {
    int i, ans = -1;
    scanf("%d %d", &N, &L);
    for (i = 0; i < N; i++) {
        scanf("%d", &set[i]);
        cnt[set[i]]++;
    }
    stable_sort(set, set + N);
    for (i = 0; i < N; i++) {
        if (set[i] >= N - i && ans < N - i) {
            ans = N - i;
        }
        if (N - i >= set[i] && ans < set[i]) {
            ans = set[i];
        }
        if (N - i >= set[i] + 1 && ans < set[i] + 1 && L >= cnt[set[i]]) {
            ans = set[i] + 1;
        }
        cnt[set[i]]--;
    }
    printf("%d", ans);
    return 0;
}