글 읽기 - 9%에서 틀렸습니다가 나오는데 어디가 틀린지 모르겠습니다.

yhw7979 5년 전 0

테스트케이스나 질문게시판에 있는 반례들을 넣어도 정답이 나와서

어디가 어떻게 틀렸는지 잘 모르겠습니다.

혹시 알려주실 분 있으신가요?

#include <iostream>

using namespace std;

void GetTotalBuildTime(int arrival, int* buildTime, int **towCon, int *alreadyArrived, int num) {
	bool isNotStart = false;

	int maxTime = 0; //사전 건물들 중 제일 시간이 오래 걸리는 건물의 건설시간(이 시간이 지나야 건물 건설 가능)
	for (int i = 0; i < arrival; i++) { //n x n행렬에서 좌측하단 부분만 사용할 것(우상단은 필요 없음)
		if (towCon[i][arrival - 1] == 1) { //이 건물의 건설에 필요한 사전 건물들이 있는 경우
			isNotStart = true; //연결점이 있으므로 시작점이 아니다.

			if (alreadyArrived[i] == -1) {//아직 건축소요시간이 계산되지 않은 경우
				GetTotalBuildTime(i + 1, buildTime, towCon, alreadyArrived, num);
			}
			if (alreadyArrived[i] > maxTime) {
				maxTime = alreadyArrived[i];
			}
		}
		if (isNotStart) {
			alreadyArrived[arrival - 1] = maxTime + buildTime[arrival - 1]; //이전 건물들의 건설 시간 중 최장시간과 자신의 건축시간을 더함
		}
		else {
			alreadyArrived[arrival - 1] = buildTime[arrival - 1];
		}
	}
}

int main(void) {
	int n;
	cin >> n;

	while (n-- > 0) {
		int towNum, towConnectNum; //건물 갯수, 건물간 연결관계 갯수

		cin >> towNum>>towConnectNum;

		int* towBuildTime = new int[towNum]; //건설필요시간
		int* towComplete = new int[towNum]; //건설완료여부
		int** towConnect = new int*[towNum]; //건물간 연결관계

		for (int i = 0; i < towNum; i++) {
			towBuildTime[i] = 0;
			towComplete[i] = -1;

			towConnect[i] = new int[towNum];
			for (int j = 0; j < towNum; j++) {
				towConnect[i][j] = 0;
			}
		}

		for (int i = 0; i < towNum; i++) {
			cin >> towBuildTime[i];
		}
		for (int i = 0; i < towConnectNum; i++) {
			int row, col;
			cin >> row>> col;

			towConnect[row-1][col-1] = towConnect[col-1][row-1] = 1;
		}

		int winTow;
		cin >> winTow;

		GetTotalBuildTime(winTow, towBuildTime, towConnect, towComplete, towNum);

		cout << towComplete[winTow-1] << endl;
	}
}

djm03178 5년 전 0

게시판을 보셨다면 매우 매우 눈에 띄는 글이 있는데 안 읽어보셨나요?

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

추가로 반례도 하나 드립니다.

1
2 1
1 1
2 1
1
정답: 2
출력: 1

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

문제

문제

출처

ICPC

9%에서 틀렸습니다가 나오는데 어디가 틀린지 모르겠습니다.

yhw7979 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말