글 읽기 - 어떤 부분에서 런타임 에러가 발생할 수 있는지 알 수 있을까요?

sjnov11 5년 전 0

안녕하세요. 일단 백준 문제가 아닌터라 카테고리를 어디로 둬야할지 몰라서 자유게시판에 올립니다.

아래는 금번 카카오 코드페스티벌 E번을 풀었던 코드입니다.

문제 링크가 닫혀서 정확하게는 알 수 없지만 기억나는대로 적어본다면

트리형태의 자료구조, 각 노드에는 score와 가수 정보가 있으며

한 노드에 가중치를 주게 된다면, 그 노드의 서브트리의 노드 갯수로 가중치를 나눠서 모든 서브트리 노드에 더해줍니다.

각 음악별 가수의 평균점수가 J가 넘게되는 time을 출력하는 것이 문제의 답입니다.

문제를 제출하고나니 런타임오류가 떴습니다.

혹시라도 인덱스 범위 초과된 참조가 있나 확인을 하였지만 찾지 못했습니다.

도움을 주신다면 대단히 감사하겠습니다.

혹시라도 코드에서 궁금하신 점 있으시다면 편하게 댓글 달아주세요!

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

class Node {
public:
	long long score;
	vector<int> child;
	int singer;
};

int N, K, J;
Node* node_list[100001];
int singer_cnt[100001];
long long singer_sum[100001];
long long singer_thresh[100001];
int singer_answer[100001];


// Tree의 크기를 반환한다.
int subtreeSize(Node* n) {
	int ret = 1;
	for (int i = 0; i < n->child.size(); i++) {
		ret += subtreeSize(node_list[n->child[i]]);
	}
	return ret;
}

// Tree를 탐색하면서 node에 해당하는 가수의 score를 더한다.
// 가수의 점수가 threshold를 넘으면 time을 체크해둔다.
void addScore(Node* n, int score, int time) {
	//n->score += score;
	if (singer_answer[n->singer] == 0) {
		singer_sum[n->singer] += score;
		if (singer_thresh[n->singer] < singer_sum[n->singer]) {
			//if (singer_answer[n->singer] == 0)
				singer_answer[n->singer] = time;
		}
	}
	for (int i = 0; i < n->child.size(); i++) {
		addScore(node_list[n->child[i]], score, time);
	}
}

int main() {
	cin >> N >> K >> J;

	// node_list 1~N까지 . 1 번 노래 부터 N번 노래까지
	for (int i = 1; i <= N; i++) {
		node_list[i] = new Node();
	}
	
	// node_list 부모. 1번이 루트니깐. 그 이후 2번부터 ~ N번 노래까지 부모 연결
	for (int i = 2; i <= N; i++) {
		int parent;
		cin >> parent;
		(node_list[parent]->child).push_back(i);
	}

	// 1~N번 노래의 가수저장. 가수의 노래 수 저장. 가수의 점수 threshold 저장. 
	for (int i = 1; i <= N; i++) {
		int n;
		cin >> n;
		node_list[i]->singer = n;
		singer_cnt[n]++;
		singer_thresh[n] += J;
	}

	// K개의 데이터 정보
	// data[시간] = (노래번호, 가중치)

	vector<pair<int, int>> data = vector<pair<int, int>>(K + 1);
	for (int i = 1; i <= K; i++) {
		int T, P, S;
		cin >> T >> P >> S;
		data[T] = make_pair(P, S);
	}

	// root , score, time : root에서부터 자손노드의 가수 점수에 score를 더한다.
	// 가수 점수가 threshold 를 넘으면 time check.
	for (int i = 1; i <= K; i++) {
		int size = subtreeSize(node_list[data[i].first]);
		int score = (data[i].second / size);
		addScore(node_list[data[i].first], score, i);
	}
	for (int i = 1; i <= N; i++) {
		int t = singer_answer[node_list[i]->singer];
		cout << "i: " << i << " ";
		if (t == 0) {
			cout << "-1" << '\n';
		}
		else
			cout << t << '\n';
	}
}

djm03178 5년 전 1

제 기억으로는 T의 범위는 10^9 이하입니다. 1부터 K까지만 시간이 있는 게 아닙니다. 즉, 아무 일도 일어나지 않는 시간이 중간에 있을 수 있습니다.

sjnov11 5년 전 0

감사합니다 ㅜㅜ

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

문제

문제

출처

ICPC

어떤 부분에서 런타임 에러가 발생할 수 있는지 알 수 있을까요?

sjnov11 5년 전 0

djm03178 5년 전 1

sjnov11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말