[백준] 2534 카드 배열

문제 주소 : www.acmicpc.net/problem/2534

2534번: 카드 배열

fast io 미적용

문제 확인

 

위상 정렬과 그리디 문제입니다.

위상 정렬 : jason9319.tistory.com/93

Topological Sort(위상 정렬)

 

풀이

 

indegree 방식 위상 정렬을 통해 카드 제약 조건을 미리 나열해서 맞는 위치에 최상의 카드를 두는 그리디 방식을 사용합니다.

최댓값을 구할 시 제약 조건 역순으로 마지막 조건에서 아래로 내려가는 방향으로 그래프를 작성합니다.

graph[b].push_back[a], indegree[a]++;

사용할 카드는 k개로 최대의 값을 내기 위해 n-k부터 사용해서 n까지 사용합니다.

최솟값을 구할 시 제약조건 순방향, k부터 0까지를 사용해서 최솟값을 만들어냅니다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<int>gph_1[300000], gph_2[300000];
    priority_queue<int, vector<int>, greater<int>>pq;
    int d_1[300000] = { 0 }, d_2[300000] = { 0 }, val[300000];
    int n, k, p;
    cin >> n >> k >> p;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        gph_1[b].push_back(a);//역순
        gph_2[a].push_back(b);
        d_1[a]++;//역순 indegree = a
        d_2[b]++;
    }
    //최댓값
    for (int i = 0; i < k; i++)
        if (!d_1[i])
            pq.push(i);
    int cur = n - k - 1;
    while (!pq.empty()) {
        int t = pq.top();
        pq.pop();
        val[t] = ++cur;//n-k -> n-1
        for (int next : gph_1[t])
            if (!--d_1[next])
                pq.push(next);
    }
    //최솟값
    for (int i = 0; i < k; i++)
        if (!d_2[i])
            pq.push(i);
    cur = k;//k -> 0
    while (!pq.empty()) {
        int t = pq.top();
        pq.pop();
        val[t] -= --cur;
        for (int next : gph_2[t])
            if (!--d_2[next])
                pq.push(next);
    }
    auto fast_pow = [](int base, int power, int m) {//함수보다 람다식이 더 빠름
        long long res = 1, t = base % m;
        while (power > 0) {
            if (power & 1)
                res = res * t % m;
            power >>= 1;
            t = t * t % m;
        }
        return res;
    };
    long long res = 0;
    for (int i = 0; i < k; i++)
        res = (res + val[i] * fast_pow(n, i, 1000000007)) % 1000000007;
    cout << res;
 
}