[ICPC] Cosmetic Survey

백준 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라서 직접 반복문을 돌리면서 저장된 값을 확인하면 된다

 

한글문제였으면 정답률이 훨씬 높지 않았을까 싶었던 문제,,

 

#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");
}