글 읽기 - 런타임 에러 원인

math_rabbit_1028 1년 전 0

OutOfBound 런타임 에러가 발생하는데 원인을 모르겠습니다.

문제에서 2 <= n<= 3000이고 전처리 후 1차원 DP를 이용해 알고리즘을 구현했습니다.

get_group는 group을 나누는 방법을 구하는 함수입니다

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
int n, adj[3030][3030], adj_sum[3030][3030], in_score[3030][3030], res[3030], dis[3030];
vector<int> group;

void get_group(int ed) {
	if (dis[ed] == -1);
	else {
		group.push_back(dis[ed]);
		get_group(dis[ed]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	// adjument metrix
	for (int i = 1; i <= n; i++) {
		while (1) {
			int a;
			cin >> a;
			if (a == 0) break;
			else {
				adj[i][a] = 1;
				adj[a][i] = 1;
			}
		}
	}
	// adj_sum
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			adj_sum[i][j] = adj_sum[i][j - 1] + adj[i][j];
		}
	}
	// in_score
	for (int i = 1; i <= n; i++) {
		in_score[i][i] = 0;
		for (int j = i + 1; j <= n; j++)
			in_score[i][j] = in_score[i][j - 1] + j - i - (adj_sum[j][j - 1] - adj_sum[j][i - 1]);
	}
	// get answer
	res[1] = 0;
	dis[1] = -1;
	for (int i = 2; i <= n; i++) {
		int min_score = 2147483647, idx = 1;
		for (int j = 1; j < i; j++) {
			// [st, i] + (i, ed]
			// [1, j] + (j, i]
			int part_score = res[j] + in_score[j + 1][i]
				+ (i * (i - 1) / 2 - in_score[1][i])
				- (j * (j - 1) / 2 - in_score[1][j])
				- ((i - j) * (i - j - 1) / 2 - in_score[j + 1][i]);
			if (min_score > part_score) {
				min_score = part_score;
				idx = j;
			}
		}
		if (min_score > in_score[1][i]) {
			res[i] = in_score[1][i];
			dis[i] = -1;
		}
		else {
			res[i] = min_score;
			dis[i] = idx; 
		}
	}
	cout << res[n] << "\n";
	get_group(n);
	sort(group.begin(), group.end());
	cout << group.size() + 1 << " " << group[0] << " ";
	for (int i = 1; i < group.size(); i++) {
		cout << group[i] - group[i - 1] << " ";
	}
	cout << n - group[group.size() - 1] << " ";
	return 0;
}

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

문제

문제

출처

ICPC

런타임 에러 원인

math_rabbit_1028 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말