1005 ACM Craft

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

1. 1516 ๊ฒŒ์ž„๊ฐœ๋ฐœ๊ณผ ๋น„์Šทํ•œ ์œ ํ˜•์ด๋‹ค
2. ์œ„์ƒ์ •๋ ฌํ•˜์—ฌ ํ‘ผ๋‹ค. ๋‹จ, 1516๊ณผ๋Š” ๋‹ค๋ฅด๊ฒŒ ๋ชฉํ‘œ๊ฑด๋ฌผ์„ ์ง€์—ˆ๋‹ค๋Š”๊ฒŒ ํ™•์ธ๋˜๋ฉด while๋ฌธ์„ ์ข…๋ฃŒํ•˜๊ณ  ์ถœ๋ ฅํ•ด๋„ ๋จ.
3. ๋‹จ, ์ง„์งœ๋กœ ์œ„์ƒ์ •๋ ฌํ•œ ๋ฐฐ์—ด์„ ๋งŒ๋“ค ํ•„์š”๋Š” ์—†๊ณ , ์œ„์ƒ์ •๋ ฌ์‹์œผ๋กœ ํ’€์–ด๋„ ์‹œ๊ฐ„์€ ๋น„์Šทํ•˜๋‹ค. ์˜คํžˆ๋ ค ์œ„์ƒ์ •๋ ฌ์„ ๊ตณ์ด ์•ˆ๋งŒ๋“œ๋Š” ํŽธ์ด ๋” ๋น ๋ฅผ ์ˆ˜์žˆ๋‹ค.
4. ๋” ๋น ๋ฅด๊ฒŒ ํ•˜๋Š” ๋ฐฉ๋ฒ•์€, ๋ชฉํ‘œ๊ฑด๋ฌผ์ด ์†ํ•œ ๊ทธ๋ž˜ํ”„๋งŒ์„ ๊ฒ€์‚ฌํ•˜๋Š” ๊ฒƒ.

๊ธฐํƒ€

1.  DP : ์™œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ถ„๋ฅ˜์— DP๊ฐ€ ๋“ค์–ด๊ฐ”๋‚˜ ํ–ˆ๋”๋งŒ, ์ด๋ฏธ ๊ฒ€์‚ฌํ•œ ๊ฑฐ๋Š” checkํ‘œ์‹œํ•˜์—ฌ ๊ฒ€์‚ฌํ•˜์ง€์•Š๊ณ , ์ตœ๋Œ“๊ฐ’์„ ๋‹ค์Œ ๋…ธ๋“œ๋กœ ๊ณ„์† ๋„˜๊ฒจ์ฃผ๋Š” ํ˜•ํƒœ๊ฐ€ DP์ธ๊ฑฐ ๊ฐ™๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#include <vector>
#define MAX_CRAFT 1000
 
using namespace std;
 
typedef struct Craft {
	int time;
	int timeTaken;
	int before;
	bool isChecked;
	vector<int> next;
} Craft;
 
Craft craft[MAX_CRAFT];
vector<int> answer;
 
int main() {
	int numOfTc;
	cin >> numOfTc;
	for (int i = 0; i < numOfTc; i++) {
		memset(craft, 0, sizeof(craft));
 
		//์ž…๋ ฅ
		int numOfCraft, numOfOrder, targetCraft;
		cin >> numOfCraft >> numOfOrder;
		for (int j = 0; j < numOfCraft; j++)
			cin >> craft[j].time;
		for (int j = 0; j < numOfOrder; j++) {
			int temp, temp2;
			cin >> temp >> temp2;
			temp--;
			temp2--;
			craft[temp].next.push_back(temp2);
			craft[temp2].before++;
		}
		cin >> targetCraft;
		targetCraft--;
 
		//๊ณ„์‚ฐ
		bool check = true;
		while (check) {
			for (int j = 0; j < numOfCraft; j++) {
				if (!craft[j].isChecked && craft[j].before == 0) {
					int tempTime = craft[j].time + craft[j].timeTaken;
					for (int k = 0; k < craft[j].next.size(); k++) {
						if (craft[craft[j].next[k]].timeTaken < tempTime)
							craft[craft[j].next[k]].timeTaken = tempTime;
						craft[craft[j].next[k]].before--;
					}
					craft[j].isChecked = true;
					if (j == targetCraft)
						check = false;
				}
			}
		}
 
		answer.push_back(craft[targetCraft].time + craft[targetCraft].timeTaken);
	}
	for (int i = 0; i < answer.size(); i++)
		cout << answer[i] << endl;
}