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;
}