[BOJ]1005: ACM Craft

문제 링크

DFS + DP 방식으로 풀었다. 위상 정렬이라는 것으로 풀 수도 있는 것 같은데 다음 시간에 다시 풀어보도록 하고...

나는 처음에 1번부터 시작해서 N까지 다 시간을 구한 후에 dp[w]을 출력해줄려고 했는데 각각의 dp[i]값을 지정해줄 방법을 생각하지 못하다가 결국 다른 분들을 보니 w부터 시작해서 (그래프라면) 위로 연결된 자신의 부모를 탐색하신 것을 봤다. 

그래서 만약 7번 노드가 5번 6번과 연결되어 있다면 dp[7] = max(dp[5], dp[6]) + 7번의 시간(d[7]) 이런 형식이였다. 그래서 이 부분은 재귀함수를 돌려서 1번 노드까지 찍고 내려오면 되는 것이였다;;

잡소리를 좀 하자면 결국 답은 인접 행렬로 풀었는데 원래 인접 리스트(vector)로 풀려다가 겁나 뻘짓해서 롤백되었다. 자주자주 문제를 풀면서 머리 속에 있는 아이디어를 적절한 방식으로 풀어낼 수 있는 능력이 길러졌으면 좋겠다. 그리고 정말 다른 분들 코드 보기 싫었는데(방식도 똑같아서) 너무 시간을 많이 쓴 탓에 나 자신에게 타협하면서 봤다. 분하다.

코드

#include <cstdio>
#include <algorithm>
using namespace std;
const int MN = 1001;
int DP[MN], ADJ[MN][MN], D[MN];

int func(int w, int n)
{
	if (DP[w] >= 0) return DP[w];
	int Max = 0;
	for (int i = 1; i <= n; ++i) {
		if (ADJ[w][i] == 1)
			Max = max(Max, func(i, n));
	}
	return DP[w] = Max + D[w];
}

int main()
{
	int t, n, k, w;
	scanf("%d", &t);
	for (int i = 0; i < t; ++i) {
		scanf("%d %d", &n, &k);
		for (int j = 0; j < MN; ++j) D[j] = 0, DP[j] = -1;
		for (int j = 0; j < MN; ++j) for (int k = 0; k < MN; ++k) ADJ[j][k] = 0;

		for (int j = 1; j <= n; ++j) scanf("%d", &D[j]);
		for (int j = 1, x, y; j <= k; ++j) {
			scanf("%d %d", &x, &y);
			ADJ[y][x] = 1;
		}
		scanf("%d", &w);
		printf("%d\n", func(w, n));
	}
	return 0;
}