백준 14864 - 줄서기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14864

14864번: 줄서기

순위를 정하는 규칙을 찾는 문제였습니다.

1 ~ N까지 순서대로 서있는 학생이 카드를 받습니다.
이때 자신이 서있는 곳보다 뒤에 있는 학생이 자신이 가지고 있는 카드의 수보다 작을 경우 해당 명단을 받습니다.
이를 통해 학생들이 가지고 있는 카드를 순서대로 알아내는 문제입니다.

예제 입력 1을 통해서 값을 확인하겠습니다.
2, 5번 학생이 1번 학생보다 뒤에 있지만 카드의 수가 작습니다.
->
1번 학생은 3을 가지고 있는 것을 알 수 있습니다.
그 이유는 첫번째로 서있는 학생이 4이상을 가지고 있다면 뒤에서 1,2,3..이 나올 것이기에 명단을 2개만 가질 수 없습니다.
4,5번 학생이 3번 학생보다 뒤에 있지만 카드의 수가 작습니다.
->
1번 학생이 3을 가지고 있어 3번 학생은 4 or 5를 가져야합니다. 만약 3번 학생이 4를 가지게 된다면 5번을 가질 수 있는 학생은 2번이 유일합니다.
하지만 2번 학생이 5를 가지게 된다면 (2, 3)의 명단도 있어야하지만 없는 것을 보아 3번 학생은 무조건 5를 가져야합니다.
5번 학생이 4번 학생보다 뒤에 있지만 카드의 수가 작습니다.
->
4번 학생이 가질 수 있는 카드의 경우는 4번, 2번, 1번입니다. 만약 4번 학생이 2번을 가지게 되면 2번 학생이 4번을 가져야 합니다.
하지만 2번 학생이 4를 가지게 된다면 (2, 4), (2, 5)의 명단이 있어야하지만 없는 것을 보아 4번 학생은 4를 가져야합니다.
같은 논리로 2번 학생이 1번, 5번 학생이 2번을 가져야 합니다.

예제 2번 또한 같은 논리로 확인해 본다면 경우가 2개가 나오는 데 모두 명단에 존재하지 않음으로 만들 수 없는 경우임을 확인할 수 있습니다.

해당 문제를 푸는 방법은 명단이 없다고 가정한 후, 명단의 수를 하나씩 대입하면서 확인하는 것입니다.
처음에는 1 ~ N번의 학생이 자기 순서와 같은 카드를 가지고 있다고 가정합니다.
이때 나오는 명단인 (X, Y) 통해 X번 학생의 카드를 1 올리고 Y번 학생의 카드를 1 내려주면서 확인하면 됩니다.
모든 명단을 확인한 후, 겹치는 등수가 있다면? -> 만들 수 없는 경우라고 해줍니다.


자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <string>
#define INF 987654321
#define P pair<int,int>
#define PP pair<int, P>
using namespace std;


int N, M;
int grade[100001];
int exist[100001];

void solve() {
	for (int i = 1; i <= N; i++) grade[i] = i;
	for (int i = 1; i <= M; i++) {
		int x, y;
		cin >> x >> y;
		grade[x]++;
		grade[y]--;
	}
	for (int i = 1; i <= N; i++) {
		if (exist[grade[i]] == 1) { // 중복된 순위가 있을 경우 -1을 출력
			cout << "-1";
			return;
		}
		exist[grade[i]] = 1;
	}
	for (int i = 1; i <= N; i++) cout << grade[i] << " ";
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	solve();
	return 0;
}

질문 및 조언 댓글 남겨주세요