(C++) 백준 14567 선수과목 (Prerequisite)

문제 및 풀이

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

(1) 위상정렬

순서가 정해져있는 문제인 위상정렬로 풀수있다 !

• 수강 후 들을 수 있는 수업의 목록을 저장할 벡터
  • a 수강 후 b 수강 가능시 v[a].push_back(b);
• 해당 수업을 듣기 위해 선수해야 할 강의 수를 저장할 배열 (cnt)

cnt=0인 값부터 queue에 넣어 벡터를 돌면서 v[x]에 있는 값들의 cnt를 1씩 줄여준다. cnt가 0이되는 값이 있으면 다시 벡터에 다시 넣고 똑같이 반복한다 ~!

#include <iostream>
#include <vector>
#include <queue>
using namespace std;


int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int N,M; cin>>N>>M;

    vector<vector<int>> v(N+1);
    vector<int> cnt(N+1, 0);
    vector<int> ans(N+1, 0);

    // a b a가 b의 선수
    int a,b;
    for(int i=0; i<M; i++){
        cin>>a>>b;
        v[a].push_back(b);
        cnt[b]++;
    }

    queue<pair<int, int>> q;
    for(int i=1; i<=N; i++) if(cnt[i]==0) q.push({i,1});

    while(!q.empty()){
        int next = q.front().first;
        int next_cnt = q.front().second;
        ans[next] = next_cnt;
        q.pop();

        for(int i=0; i< (int) v[next].size(); i++){
            int x = v[next][i];
            cnt[x]--;
            if(cnt[x]==0) q.push({x, next_cnt+1});
        }
    }

    for(int i=1; i<=N; i++) cout<<ans[i]<<" ";
}

(2) 다이나믹 프로그래밍

• dp[x] = max(기존 x를 듣기 위해 필요한 학기 수, x의 선수과목을 듣기 위해 필요한 학기 수 +1)
  • 선수과목 수강 후 다음수업을 들을 수 있으므로 (선수과목+1) 학기와 기존에 필요한 학기를 비교하여 더 큰 값을 답으로 한다.
  • 선수과목이 더 작은 수라는 조건이 있어서, 문제 input을 모두 입력받고 작은 선수과목부터 먼저 dp 테이블을 채워줘야 틀리지 않는다 !

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int N,M; cin>>N>>M;

    vector<pair<int, int>> v;
    vector<int> dp(N+1, 1);

    // a b a가 b의 선수
    int a,b;
    for(int i=0; i<M; i++){
        cin>>a>>b;
        v.push_back({b,a}); // b 듣기 위해 a 수강
    }

    sort(v.begin(), v.end());

    for(int i=0; i<M; i++){
        int pre = v[i].second;
        int next = v[i].first;
        dp[next] = max(dp[next], dp[pre]+1);
    }

    for(int i=1; i<=N; i++) cout<<dp[i]<<" ";

}