백준 16358번으로 풀어본 Icpc 예선 문제
문제가 너무 길어서 읽기 싫었지만 문제 해석만 꼼꼼히 하면 의외로 쉬운 문제
input 크기가 작아서 3중 for문 까지 가능ㅎㅎ
문제가 복잡하니 조건을 정리해보자면
- 각 평가자들은 양의 정수로 rank를 주고 수가 적을수록 선호도가 높은 것이다
- rank는 유일하거나 연속하지 않다
- rank를 매기지 않았다면 선호도 우선순위에서 제외된다
각 사용자별 선호도를 입력 받은 후 d(X,Y)라는 notation에 맞추어 d 배열을 만들었다
이 배열은 X보다 Y를 확실히 선호하는 사람의 수이다
input 배열을 돌면서 각 사용자의 확실한 선호도가 존재하는 경우 d배열의 적절한 index를 증가시켜주었다
그다음 플로이드 와샬 알고리즘과 비슷하게 경유지를 정해서 3중 for문을 사용하였다
경유하는 느낌으로 i->j를 i->k,k->j로 잘라주고 preference index 값은 path에서의 가중치의 최소값이니까 i->k,k->j 중 작은값을 선택해주었다
이 작은값은 기존의 i->j와 비교하는데 preference strength의 값은 모든 path의 preference index에서의 최대값이니까 둘 중 큰 값으로 d[i][j]를 갱신해주었다
이 부분 해석이 가장 헷갈렸다ㅜㅜ
마지막으로 출력 또한 문제에서 하라는대로만 하면 된다
S(X,Y)는 모든 Y에 대하여 S(X,Y) >= S(Y,X)를 만족하면 most preferred라서 직접 반복문을 돌리면서 저장된 값을 확인하면 된다
한글문제였으면 정답률이 훨씬 높지 않았을까 싶었던 문제,,
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <stdio.h>
#include <algorithm>
using namespace std;
int input[505][505]; // evaluator, rank
int d[505][505]; // d[i][j] = number of evaluators who strictly prefer i to j
int main(){
int m,n;
scanf("%d %d",&m,&n);
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= m ; j++) scanf("%d",&input[i][j]);
}
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= m ; j++){
// increase every product which has higher rank (smaller number) than j, evalutor : i
if(input[i][j]==0) { // unrank
for(int k = 1 ; k <= m ; k++){
if(input[i][k]!=0) d[k][j]++;
}
}
else{ // rank
for(int k = 1 ; k <= m ; k++){
if(input[i][k]!= 0 && input[i][j]>input[i][k]) d[k][j]++;
}
}
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
// one of i -> j , j -> i , no connection
if(d[i][j] == d[j][i]) d[i][j] = d[j][i] = 0;
else if(d[i][j] < d[j][i])d[i][j] = 0;
else d[j][i] = 0;
}
}
for(int k = 1; k <= m; k++){ // 경유지
for(int i = 1; i <= m; i++){ // from
for(int j = 1; j <= m; j++){ // to
d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
}
}
}
for(int i = 1; i <= m; i++){
int j;
for(j = 1; j <= m; j++){
if(i == j)continue;
if(d[i][j] < d[j][i]) break;
}
if(j>m) printf("%d ",i);
}
printf("\n");
}
|
cs |
'알고리즘' 카테고리의 다른 글
[C] 달리기 (0) | 2021.02.06 |
---|---|
[C++] 게임 (0) | 2021.02.05 |
[ICPC] Rectilinear Regions (0) | 2020.09.30 |
[ICPC] Philosopher’s Walk (0) | 2020.09.29 |
[ICPC] Parentheses (0) | 2020.09.24 |