글 읽기 - 1005. 시간초과 문제

sjnov11 5년 전 0

안녕하세요,

1005번 문제를 푸는데 도통 무엇 때문에 시간초과가 되는지 잘 이해가 가지 않아 질문 드립니다.

혹시 확인해주실수 있으신가요?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int p[1001];
int dp[1001];
vector<int> order[1001];

int solve(int W) {
	if (dp[W] > 0) {
		return dp[W];
	}
	int prev_max = 0;
	for (int i = 0; i < (order[W]).size(); i++) {
		int prev = order[W][i];
		if (dp[prev] == 0)
			solve(prev);
		prev_max = max(prev_max, dp[prev]);
	}
	dp[W] = prev_max + p[W];
	return dp[W];
}


int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;

	for (int test_case = 0; test_case < T; test_case++) {
		int N, K;
		cin >> N >> K;
		for (int i = 1; i <= N; i++) {
			cin >> p[i];
		}
		for (int i = 0; i < K; i++) {
			int prev, next;
			cin >> prev >> next;
			order[next].push_back(prev);
		}

		int W;
		cin >> W;
		cout << solve(W) << endl;
		

		for (int i = 1; i <= N; i++) {
			dp[i] = 0;
			order[i].clear();
		}
	}

}

djm03178 5년 전 0

https://www.acmicpc.net/board/...

sjnov11 5년 전 0

시간 D 의 범위가 0이 포함이었네요. 감사합니다.

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

문제

문제

출처

ICPC

1005. 시간초과 문제

sjnov11 5년 전 0

djm03178 5년 전 0

sjnov11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말