[BOJ/백준][Gold4] 14864 : 줄서기 (C++)

https://www.acmicpc.net/problem/14864

14864번: 줄서기

 

[난이도] Gold4
[유형] ad hoc

[풀이]
안풀려서 다른 사람의 풀이를 참고하였다.
ad hoc 문제라고 한다. bfs,dfs,dp 등 정형화된 문제유형이 아닌 해당 문제에만
특화된 풀이법으로 풀어야 하는 문제라고 한다. (창의적으로..)

이 문제는 배열 a[i]=i (i:1~N) 으로 설정해놓고
(u,v) 쌍에 대해 a[u]++,a[v]-- 를 해주면 답이 나온다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/14864.cpp

 

#include <cstdio>
int N,M,a[100001],exist[100001];
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) a[i]=i;
    while(M--){
        int u,v;
        scanf("%d%d",&u,&v);
        a[u]++,a[v]--;
    }
    for(int i=1;i<=N;i++) {
        if(exist[a[i]]){
            puts("-1");
            return 0;
        }
        exist[a[i]]=1;
    }
    for(int i=1;i<=N;i++) printf("%d ",a[i]);
}