글 읽기 - ACM Craft 어디서 틀렸는지 모르겠어요.

dhmin5693 3년 전 0

dp로 풀었고 테스트 케이스는 출력이 잘 됩니다.

a는 원본, dp는 답을 구할 배열로 사용했습니다.

문제에서 요구하는 [최소 몇 초가 필요하느냐]에 대해서는

주어진 건물 순서 x, y에서 x에 속하는 건물들 중 가장 긴 시간을 소모한 건물 + y를 짓는데 소요되는 시간으로 생각하였습니다.

어떤 점에서 틀린 건가요?

#include <cstdio>
#define max(a, b) (a) > (b) ? (a) : (b)

int main()
{
	int t;

	for (scanf("%d", &t); t > 0; t--)
	{
		int n, k;
		scanf("%d %d", &n, &k);

        int a[1010] = { 0 }, dp[1010] = { 0 };
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
			dp[i] = a[i];
		}

		for (int i = 0; i < k; i++)
		{
			int x, y;
			scanf("%d %d", &x, &y);
			dp[y - 1] = max(dp[y - 1], a[y - 1] + dp[x - 1]);
		}

		int w;
		scanf("%d", &w);

		printf("%d\n", dp[w - 1]);
	}

	return 0;
}

djm03178 3년 전 1

먼저 지어야 하는 건물 순으로 입력이 들어온다는 보장이 없습니다.

3 2

3 3 3

2 1

3 2

답은 9이지만, 6이 출력됩니다.

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

문제

문제

출처

ICPC

ACM Craft 어디서 틀렸는지 모르겠어요.

dhmin5693 3년 전 0

djm03178 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말