IOI2009 3번 POI

문제 링크

  • http://icpc.me/5462

문제 출처

  • 2009년 국제 정보 올림피아드 3번 (Day1 3번)

시간복잡도

  • O(NT)

풀이

단순 구현 문제입니다.

문제별로 점수를 계산해준 뒤, 아래 코드처럼 필립보다 잘 본 사람의 수를 직접 카운팅해도 되고, 정렬을 이용해 해결할 수도 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

vector<int> user[2020];
int problemScore[2020];
int userScore[2020];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, t, p; cin >> n >> t >> p;

	for(int i=1; i<=t; i++){
		problemScore[i] = n;
	}

	for(int i=1; i<=n; i++){
		for(int j=0; j<t; j++){
			int x; cin >> x;
			if(!x) continue;
			user[i].push_back(j+1);
			problemScore[j+1]--;
		}
	}

	for(int i=1; i<=n; i++){
		for(auto x : user[i]){
			userScore[i] += problemScore[x];
		}
	}

	int ans = 1;
	for(int i=1; i<=n; i++){
		if(i == p) continue;
		if(userScore[i] > userScore[p]) ans++;
		else if(userScore[i] == userScore[p]){
			if(user[i].size() > user[p].size()) ans++;
			else if(user[i].size() == user[p].size() && i < p) ans++;
		}
	}
	cout << userScore[p] << " " << ans;
}