2056 task

์•Œ๊ณ ๋ฆฌ์ฆ˜(์œ„์ƒ์ •๋ ฌ)

1. Task ๊ตฌ์กฐ์ฒด๋ฅผ ์„ ์–ธํ•˜์—ฌ, time : ํ˜„์žฌ task๊ฐ€ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ์ €์žฅ / timeTaken : ํ˜„์žฌ๊นŒ์ง€ ์˜ค๋Š”๋ฐ ์„ ํ–‰์œผ๋กœ ํ•„์š”ํ•œ ์ž‘์—…์„ ์ˆ˜ํ–‰ํ•˜๋ฉด์„œ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„ ์ค‘ ๊ฐ€์žฅ ๊ธด ์‹œ๊ฐ„ ์ €์žฅ
			next : ๋‹ค์Œ์œผ๋กœ ์ด์–ด์ง€๋Š” ์ž‘์—…๋“ค์„ ์ €์žฅ
2. Task ๊ตฌ์กฐ์ฒด ๋ฐฐ์—ด์„ ์•ž์—์„œ๋ถ€ํ„ฐ ๊ฒ€์‚ฌ
	-> ํ˜„์žฌ task์˜ time๊ณผ timeTaken์„ ๋”ํ•ด temp์— ์ €์žฅ.
	-> ์ด์–ด์ง€๋Š” ์ž‘์—…๋“ค์„ ํ•˜๋‚˜์”ฉ ๊ฒ€์‚ฌ -> ์ด์–ด์ง€๋Š” ์ž‘์—…์˜ timeTaken๋ณด๋‹ค ํ˜„์žฌ์˜ temp๊ฐ€ ๋” ๊ธธ๋ฉด temp๋ฅผ ์ €์žฅ
	-> ๊ฒ€์‚ฌ๊ฐ€ ๋๋‚˜๊ณ  ํ˜„์žฌ์˜ temp๊ฐ€ ์ „์ฒด temp์ค‘ ๊ฐ€์žฅ ํฐ์ง€ ๊ฒ€์‚ฌ.(๊ทธ๋ƒฅ ์ด์–ด์ง€๋Š” ์ž‘์—… ๊ฒ€์‚ฌ ๋๋‚˜๊ณ  ๋ฐ”๋กœ maxTime ๊ฒ€์‚ฌํ•˜๋ฉด ๋จ)
3. ๋ฒˆํ˜ธ์™€ ์„ ํ–‰๊ด€๊ณ„๊ฐ€ ๋’ค์ฃฝ๋ฐ•์ฃฝ์ด ์•„๋‹Œ, ์„ ํ–‰ ์ž‘์—…์€ ๋ฌด์กฐ๊ฑด ํ˜„์žฌ๋ฒˆํ˜ธ๋ณด๋‹ค ์•ž์— ์žˆ์œผ๋ฏ€๋กœ ๊ทธ๋ƒฅ for๋ฌธ์œผ๋กœ ์•ž์—์„œ๋ถ€ํ„ฐ ๊ฒ€์‚ฌํ•˜๋ฉด ๋œ๋‹ค.

ํ‰๊ฐ€.

์„ ํ–‰๊ด€๊ณ„๊ฐ€ ๋˜‘๋ฐ”๋กœ ๋ผ์žˆ์–ด์„œ ์•„์ฃผํŽธํ•˜๊ฒŒ ์ฝ”๋”ฉํ•จ

์ฝ”๋“œ

#include <iostream>
#include <vector>
#define MAX_TASK 10000
 
using namespace std;
 
typedef struct Task {
	int time;
	int timeTaken;
	vector<int> next;
} Task;
 
Task task[MAX_TASK];
int numOfTask;
 
int minTimeComplete();
 
int main() {
	cin >> numOfTask;
	for (int i = 0; i < numOfTask; i++) {
		cin >> task[i].time;
		int numOfBefore;
		cin >> numOfBefore;
		for (int j = 0; j < numOfBefore; j++) {
			int before;
			cin >> before;
			task[before-1].next.push_back(i);
		}
	}
 
	cout << minTimeComplete();
}
 
int minTimeComplete() {
	int maxTime = 0;
	for (int i = 0; i < numOfTask; i++) {
		int time = task[i].time + task[i].timeTaken;
		for (int j = 0; j < task[i].next.size(); j++)
			task[task[i].next[j]].timeTaken = task[task[i].next[j]].timeTaken > time ? task[task[i].next[j]].timeTaken : time;
		maxTime = maxTime > time ? maxTime : time;
	}
	return maxTime;
}