BOJ 2534 카드 배열

문제 링크입니다.

문제 요약

각 자리수가 서로 다른 $k$자리의 $N$진수 중, 주어진 자리수 간 대소 조건을 모두 만족하는 수의 최댓값과 최솟값의 차를 구하세요.

풀이

최댓값과 최솟값을 구하는 건 본질적으로 같은 작업입니다. 최댓값을 구하는 방법만 알면, 이를 대칭적으로 적용해 최솟값을 구할 수 있어요.

모든 자리수가 서로 달라야 한다는 조건 때문에, 가능한 최대의 $N$진수의 각 자리수에는 $N-1$부터 $N-k$까지의 숫자가 한 번씩 사용되어야 함을 알 수 있습니다. 만약 그렇지 않다면, 모든 대소 관계를 유지하면서 $N-1$부터 $N-k$까지의 숫자로 각 자리수를 바꿨을 때 값이 더 커지므로 모순입니다.

이제 주어진 대소 조건에 따라 가장 큰 숫자를 최대한 왼쪽에 배치하면 문제를 해결할 수 있겠네요. 대소 조건이 올바르게 주어졌다면 이는 DAG를 구성하기 때문에, 수의 각 자리를 위상 정렬한 뒤 순서대로 채우면 되겠거니 할 수 있습니다. 그래서 큰 값 –> 작은 값 쪽으로 간선을 만든 뒤 그리디하게 넣을 수 있는 가장 왼쪽 칸에 가장 큰 값을 넣으면 WA를 받습니다.

!?

위 그리디의 반례로는, 맨 왼쪽 자리가 맨 오른쪽 자리보다 작아야 하는 경우를 생각해 볼 수 있습니다. 적당히 길이를 4라고 하면, 위의 전략에 따라 값을 채우면 답이 1432가 나옵니다. 실제 최적해인 3124보다 작네요.

그럼에도 불구하고 위상 정렬을 이용해 그리디를 수행하는 아이디어가 틀린 건 아닙니다. 다만 그 간선의 방향을 뒤집어, 작은 값 –> 큰 값 쪽으로 향하게 간선을 설정한 뒤 가장 오른쪽부터 작은 숫자로 채워나가야 합니다. 최대한 적은 제약 조건 안에서 큰 수를 왼쪽으로 몰아넣을 수 있도록 작은 쪽부터 제약 조건을 해소해 주는 느낌 정도로 직관적으로 이해할 수 있을 것 같네요.

우선순위 큐 등의 자료 구조를 이용해 위상 정렬을 구현하면 총 시간 복잡도 ${\cal O}(N \lg N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
ll n, k, p, l, r;
vector<vector<int>> hie, loe;
int hideg[303030], lodeg[303030], hi[303030], lo[303030];
priority_queue<int> lopq, hipq;
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	cin >> n >> k >> p;
	hie.resize(k); loe.resize(k);
	while(p--){
		int u, v; cin >> u >> v;
		hie[v].push_back(u);
		hideg[u]++;
		loe[u].push_back(v);
		lodeg[v]++;
	}
	l = k-1; r = n-k;
	for(int i = 0; i < k; i++){
		if(!lodeg[i]) lopq.push(-i);
		if(!hideg[i]) hipq.push(-i);
	}
	while(lopq.size()){
		int now = -lopq.top(); lopq.pop();
		lo[now] = l--;
		for(auto nxt : loe[now]) if(!--lodeg[nxt]) lopq.push(-nxt);
	}
	while(hipq.size()){
		int now = -hipq.top(); hipq.pop();
		hi[now] = r++;
		for(auto nxt : hie[now]) if(!--hideg[nxt]) hipq.push(-nxt);
	}
	ll ans = 0;
	for(int now = k-1; now >= 0; now--){
		ans = ans*n%mod;
		ans += hi[now]-lo[now]+2*mod;
		ans %= mod;
	}
	cout << ans;
}