10159

처음에 이 문제를 읽을때 위상정렬을 써야하나 깊이 고민했는데

올림피아드 문제에서 대학생들이 공부하는 위상정렬을 여기서 쓰겟나 싶어서 간단히 접근한결과 무식하게 풀기를 생각해냈다.

이차원 배열을 선언하고 다음과 같이 정의한다.

judge[from][to] from과 to의 값을 비교 결과를 저장하는 배열이다. 

from< to이면 -1, from > to 이면 1, 알수 없으면 0으로 저장한다.

여기서 너무도 당연한 사실을 생각 할 수 있는데

from < to 이면

from과 from보다 작은 값들과, to와 to보다 높은 값들과 비교를 할 수 있다는 사실

그래서 난 from과 from보다 작은 값들을 loser라는 벡터에 두고

to와 to보다 높은 것들을 winner라는 벡터에 두어서

(judge[][]함수를 찾아다녔다)

각각 벡터 값으로 judge[][]를 재정의 해주는 방법을 택했다.

알고리즘의 시간 복잡도는 O(N*N)으로 좋지 않지만

문제에서 크기를 100으로 제한했기 때문에 시간내에는 충분히 풀 수 있는 문제.

#include<iostream> #include<cstdio> #include<vector> using namespace std; int judge[105][105]; int main() { int N, M, from, to; scanf("%d %d", &N, &M); while(M--) { scanf("%d %d", &from, &to); vector<int> losers, winners; losers.push_back(from); winners.push_back(to); for(int loser=0; loser<=100; loser++) { if(judge[loser][from]==-1) { losers.push_back(loser); } } for(int winner=0; winner<=100; winner++) { if(judge[winner][to]==1) { winners.push_back(winner); } } for(int l=0; l<losers.size(); l++) { for(int w=0; w<winners.size(); w++) { judge[losers[l]][winners[w]]=-1; judge[winners[w]][losers[l]]=1; } } } for(int piv=1; piv<=N; piv++) { int res=0; for(int k=1; k<=N; k++) if(judge[piv][k]!=0) res++; printf("%d\n", N-res-1); } return 0; }