[백준/C++] 1005. ACM Craft

문제

www.acmicpc.net/problem/1005

1005번: ACM Craft

풀이

DP로 풀면 된다!

cache[i]: i를 짓는데 까지 걸리는 시간

 

i를 짓는데 걸리는 시간을 찾는 함수에서,

1) cache값이 있으면 바로 return

2) 없으면, 새로 구해서 cache에 채워넣고 return 한다 

• i를 짓는데 걸리는 시간 = i 건설 시간 + max( i전에 지어야 하는 건물들의 건설 시간 )

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int rules[1001][1001];
int times[1001];
int cache[1001];
int N;

//rules[i][j] : i를 지은 다음에 j를 지어야 한다 
//times[i] : i만 짓는데 걸리는 시간

//cache[i] : i를 짓기까지 걸리는 시간 (DP)

int timesForW(int w) {
	if (cache[w] != -1)
		return cache[w];
	
	int answer = 0;
	for (int i = 1;i <= N; i++) {
		if (rules[i][w] == 1) {
			answer = max(timesForW(i),answer);
		}
	}
	answer += times[w];
	cache[w] = answer;
	
	return answer;
}
int main(void) {
	int T, K, W;
	cin >> T;
	for (int t = 0;t < T;t++) { //testcase수 만큼 반복
		cin >> N >> K;
		fill(&rules[0][0], &rules[1000][1001], 0);
		fill(&times[0], &times[1001], 0);
		fill(&cache[0], &cache[1001], -1);
		for (int n = 1; n <= N;n++) {
			cin >> times[n];
		}
		for (int k = 0;k < K; k++) { //규칙 입력받기 
			int x, y;
			cin >> x >> y;
			rules[x][y] = 1;
		}
		cin >> W;
		cout << timesForW(W) << endl;
	}
	return 0;
}

결과