글 읽기 - 틀렸습니다가 계속 뜨는데 반례좀 찾아주실 분 있나요??

goodjaeheui 4년 전 0

소스코드에 내용 주석 다 달아놨습니다.

배열 초기화라던지 기본적인 것들은 문제가 없는거 같고 반례가 있어서 그런거 같은데 혹시 찾아주실 분 계신가요?

#include <iostream>
using namespace std;

// #1005 ACM Craft
#include <vector>
#define N 1001

int MAX(int a, int b) {
	return a > b ? a : b;
}

int main() {
	int t, n, k;
	int x, y;
	int w;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int arr[N];
		int dp_max[N];

		vector<int> v[N];
		cin >> n >> k;
		for (int j = 1; j <= n; j++) {//건물짓는데에 걸리는 시간
			cin >> arr[j];
		}

		dp_max[1] = arr[1];//1에서 시작하므로 시간은 arr[1]
		for (int j = 1; j <= k; j++) {// 높은번호에서 낮은번호로 노드간 단방향 연결 
			cin >> x >> y;
			v[y].push_back(x);
		}
		cin >> w;// 최종 건물 번호

		for (int j = 2; j <= n; j++) {// 알고리즘
			int max = 0;
			for (int k = 0; k < v[j].size(); k++) {
				max=MAX(max, dp_max[v[j][k]]);//연결된 하위 노드중에서(병령연결된 노드) 
			}//가장 시간이 오래 걸리는것을 max로 둠
			dp_max[j] = arr[j] + max;
		}
		cout << dp_max[w] << endl;
	}
}

djm03178 4년 전 0

https://www.acmicpc.net/board/view/30959 2번에 힌트가 있습니다.

goodjaeheui 4년 전 0

아... 네.. 꼭 1번에서 시작하라는 말이 없었군요

감사합니다!!

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

문제

문제

출처

ICPC

틀렸습니다가 계속 뜨는데 반례좀 찾아주실 분 있나요??

goodjaeheui 4년 전 0

djm03178 4년 전 0

goodjaeheui 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말