[C/C++] 백준 25168번 - 게으른 아리를 위한 접종 계획

✏️ 문제 링크

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

25168번: 게으른 아리를 위한 접종 계획

✏️ 문제 풀이

 위상정렬을 이용해서 풀었고 백신의 유효기간에 주의하여서 문제를 접근하였습니다.

 이 부분에서 경우의 수가 나눠지게 됩니다. 두 백신간의 최소 대기기간이 일주일 이상 넘어가게 되는 경우와 그렇지 않은

  경우로 나누어서 풀어야 합니다. 이것만 주의한다면 일반적인 위상정렬 문제와 다를게 없습니다.

 일주일 이상 넘어가게 되는 경우 : ans[next] = max(ans[next], ans[node] + time+1);

 일주일 이내인 경우 : ans[next] = max(ans[next], ans[node] + time);

 max(ans)값을 출력하면 됩니다

 

✏️ 문제 코드

#include<iostream>
#include<queue>
#include<vector>
#include<limits.h>
using namespace std;

typedef pair<int, int>cur;
vector<vector<cur>>mlist;
vector<int>ans;
vector<int>indegree;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	mlist.resize(N + 1);
	indegree.resize(N + 1);
	ans.resize(N + 1);


	for (int i = 0; i < M; i++) {
		int start, end, time;
		cin >> start >> end >> time;
		mlist[start].push_back(make_pair(end, time));
		indegree[end]++;
	}

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

	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for (cur temp : mlist[node]) {
			int next = temp.first;
			int time = temp.second;
			indegree[next]--;
			if(time>=7)
				ans[next] = max(ans[next], ans[node] + time+1);
			else
				ans[next] = max(ans[next], ans[node] + time);
			if (indegree[next] == 0)
				q.push(next);
		
		}
	}
	int max = INT_MIN;
	for (int i = 1; i <= N; i++) {
		if (max < ans[i])
			max = ans[i];
	}
	
	cout << max;
}