글 읽기 - DP 시간 초과 문제

devouring123 5년 전 0

예제는 제대로 작동하는거 같은데 어디서 시간 초과가 나는지 잘 모르겠네요.

DP구현을 잘 못한건가요?

DP[n]>0 인경우는 중간에 내부 for문 안에 들어있어서 물어봅니다.

#include <iostream>
#include <vector>
using namespace std;
#define MAX(X,Y) (X)>(Y)?(X):(Y)
// i번째 건물을 짓는데 걸리는 시간
int time[1001];

// i번째 건물을 짓는데 걸리는 최대 시간
int dp[1001];

// i, j번째 건물의 상관관계도
vector<int> build_tech[1001];

// 재귀형식으로 구현
// 마지막으로 지어야 하는 건물과 빌드테크를 입력으로 받고
// 그 건물을 지었을 때의 총 시간 출력
int build(int last_build) {
	int time_build = 0;
	if (!last_build)
		return 0;
	if (dp[last_build])
		return dp[last_build];
	else if (build_tech[last_build].size() == 0)
	{
		dp[last_build] = time[last_build];
		return dp[last_build];
	}
	// 이 건물을 짓기 전에 필요한 건물 서치
	else {
		for (int i = 0; i < build_tech[last_build].size(); i++)
		{
			// 값이 저장되어 있는 경우
			if (dp[build_tech[last_build][i]])
			{
				time_build = time[last_build] + dp[build_tech[last_build][i]];
				if (time_build > dp[last_build])
					dp[last_build] = time_build;
			}
			// 값이 저장 되어 있지 않은 경우
			else
			{
				time_build = time[last_build] + build(build_tech[last_build][i]);
				if (time_build > dp[last_build])
					dp[last_build] = time_build;
			}
		}
		return dp[last_build];
	}
}

int main()
{
	int N;
	cin >> N;
	while (N--)
	{
		// 입력
		int build_num, rule_num, first_build, second_build, last_build;
		
		scanf("%d %d", &build_num, &rule_num);
		//cin >> build_num >> rule_num;

		for (int i = 1; i <= build_num; i++)
			scanf("%d", &time[i]);
			//cin >> time[i];

		for (int i = 1; i <= rule_num; i++) {
			scanf("%d %d", &first_build, &second_build);
			//cin >> first_build >> second_build;
			build_tech[second_build].push_back(first_build);
		}
		scanf("%d", &last_build);
		//cin >> last_build;
		// 모든 건물 지음
		int total_time = build(last_build);
		printf("%d\n", total_time);
		// 리셋
		for (int i = 1; i <= build_num; i++)
			dp[i] = 0;
		for (int i = 1; i <= build_num; i++)
			build_tech[i].clear();
	}
}

kipa00 5년 전 0

D가 0이 될 수 있습니다.

devouring123 5년 전 0

D가 last_build 말씀하시는건가요? 아니면 dp배열 내부값이 0이 되는 것을 말씀하시는건가요?

last_build가 0이 될때 처리해서 올렸습니다. 그러나 이렇게 해도 느리네요

cin cout 속도가 느리기때문에 속도를 증가시키려고 printf scanf를 사용했는되도 시간 초과가 나네요

재귀함수로 안짜면 위상정렬밖에 답이 없는것 같은데 위상 정렬을 배우지 않아서 재귀로 짜보려고 한건데 조금 힘드네요 ㅠㅠ

sotter1020 5년 전 0

건물은 1번 부터 시작이기 때문에 last_build가 0일 될 경우의 수는 없지 않나요?
건물의 가중치 값은 0이상이기 때문에 dp가 0일 수도 있습니다. 3번 건물까지의 가중치를 구하는데 1,2,3이 다 0일 수도 있으니깐요. dp 초기를 -1로 하던가.. 경우의수가 없는수로해야 할 것 같습니다.
그래서 만약 초기값이 아니라 결과값이 dp 0이 들어있을 경우 계속해서 재귀로 함수를 호출하게 될것입니다. 그래서 한번 갔던 루트도 또 재귀하게 되겠네요.
입출력때문에 시간이 오버되는거 같진 않고, 저는 재귀로 cout, cin썼는데 통과했습니다.

devouring123 5년 전 0

D가 0 이될수 있다는것이 그런말이군요. 풀었습니다. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DP 시간 초과 문제

devouring123 5년 전 0

kipa00 5년 전 0

devouring123 5년 전 0

sotter1020 5년 전 0

devouring123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말