13333 Q-인덱스 (Q-Index)

Q-인덱스 (13333 Q-Index)

http://boj.kr/13333

열라 쉬운 문제.

근데, 문제 설명이 이상하다 ㅡ,.ㅡ;;

이건 설명이 애매모호한게 아니라 잘못 낸거 같다.

이 문제는 문제 처음 설명보다 예제에서 말하는 순서대로 고려해주면 정확히 이해가 된다.

한 학생이 발표한 총 n ≥ 1 편의 논문 중에서, k번 이상 인용된 논문이 k편이고 나머지 n − k 편의 논문들 인용회수가 각각 k 번 이하라면, 해당 학생의 q-인덱스는 k이다.

이 부분을 다음과 같이 바꾸는게 맞다.

한 학생이 발표한 총 n ≥ 1 편의 논문 중에서, k번 이상 인용된 논문이 k편 이상일 때, 여기서 선택된 k편의 논문을 제외한 나머지 n-k편의 논문들 인용횟수가 각각 k번 이하라면, 해당 학생의 q-index는 k이다.

학교 교수님이 내가 acm에서 이 문제를 틀렸다고 하는데, 나는 이 문제를 오늘 처음 봤다. (난 틀린적 없다구~!)

교수님이 이 문제를 알고리즘 수업듣는 애들에게 과제로 내줘서 한번 풀어봤음. (아무래도 우리 학생들이 이 문제 찾아보면 내 블로그를 방문하겠지. ㅋㅋ)

#include <cstdio> #include <algorithm> #include <vector> using namespace std; vector<int> v; int main() { int n; scanf("%d",&n); v.clear(); v.resize(n); for(int i=0; i<n; i++) scanf("%d", &v[i]); sort(v.begin(), v.end()); for(int k=0; k<=n; k++) { auto it = lower_bound(v.begin(), v.end(), k); int l=v.end()-it; if(l>=k && v[n-k-1]<=k) return 0&printf("%d\n", k); } return 0; }

가장 많이 틀리는 테스트 케이스는 다음과 같다.

5
3 99 98 97 96

답은 3이 아니라 4다.