글 읽기 - 왜 런타임 에러인지 모르겠습니다ㅠㅠ (C++)

harinboy 5년 전 0

알고리즘은 맞는 거 같고,

제가 생각할 수 있는 대부분의 상황에서 잘 돌아갑니다.

그런데 틀리면 틀렸지, 10번째 런타임 에러를 받고 있네요ㅠㅠ

배열 크기가 문제인가 싶어서 계속 배열에 뭐가 들어가는지 확인도해봤는데 답이 나오지 않습니다.

n, m, b를 최대치로 놓고 돌려도 잘 돌아가더라구요.

그 다음으로 걸리는건 while문인데 얘도 num이 계속++되니까 언젠가는 탈출해야하고요....

고수님 분들, 도와주세요!!

#include <stdio.h>

long long dijk[21000][102];
int d[21000][21000];
int check[21000];
int n, m, b, r, t, i, j, x, y, z;



int main(void){
	int temp, num;
	long long min;
	scanf("%d %d %d %d %d", &n, &m, &b, &r, &t);
	for (i = 0; i < r; i++){
		scanf("%d %d %d", &x, &y, &z);
		d[x][y] = z;
		d[y][x] = z;
	}
	for (i = 1; i <= b; i++){
		for (j = 1; j <= n + m + b; j++){
			check[j] = 0;
		}
		check[n + m + i] = 1;
		num = 1;
		for (j = 1; j <= n + m + b; j++){
			dijk[j][i] = (long long)d[i+n+m][j];
		}
		while (num < n + m + b){
			temp = n + m + i;
			min = 0;
			for (j = 1; j <= n + m + b; j++){
				if (check[j] == 0 && dijk[j][i] != 0){
					if (min == 0 || min > dijk[j][i]){
						min = dijk[j][i];
						temp = j;
					}
				}
			}
			if (temp == n + m + i) break;
			check[temp] = 1;
			dijk[temp][i] = min;
			num++;
			for (j = 1; j <= n + m + b; j++){
				if (check[j] == 0 && d[j][temp] != 0){
					if (dijk[j][i] == 0 || dijk[j][i]>dijk[temp][i] + (long long)d[j][temp]){
						dijk[j][i] = dijk[temp][i] + (long long)d[j][temp];
					}
				}
			}
		}
	}
	for (i = 0; i < t; i++){
		scanf("%d %d", &x, &y);
		min = 0;
		for (j = 1; j <= b; j++){
			if ((min == 0 || min > dijk[x][j] + dijk[y][j]) && dijk[x][j] > 0 && dijk[y][j] > 0){
				min = dijk[x][j] + dijk[y][j];
			}
		}
		if (min == 0){
			printf("-1\n");
		}
		else{
			printf("%lld\n", min);
		}
	}
}

rdd6584 5년 전 0

d배열의 크기가 너무 큽니다.

메모리초과 대신 런타임을 받으신 게 아닌가 생각듭니다.

rdd6584 5년 전 0

위 문제는 간선정보를 배열로 표현하기에는 정점의 개수가 너무 많고, 한 정점에서 다른 정점으로 가는 간선이 여러 개일 경우를 처리해주지 못합니다. 동적배열이나 stl의 vector같은 구조를 사용하셔야 할 듯 합니다.

chogahui05 5년 전 0

21000^2 = 4.41억이군요.. int형 하나당 4byte이므로

16.41억 바이트 = 1641백만byte = 1641M = 1.6G

harinboy 5년 전 1

감사합니다!

런타임 에러를 안 띄우는거에 급급하다보니까 다른 생각을 전혀 못했네요ㅠㅠ

차라리 메모리 초과라고 솔직하게 알려줬으면 그래도 일찍 알았을 텐데

알고리즘은 알아도 코딩은 초보라 벡터 이런거 처음 써보고 열심히 배워서 결국 맞았습니다를 얻어냈습니다!!

네블컵 재미있게 참가했구요 조악한 코드 읽어주셔서 감사합니다.

chogahui05 5년 전 0

ㄷㄷ 돌떡 푸셨네요. ㄷㄷ

전 젤 어려운 문제로 봤는데.. ㄷㄷ..

이 참에 중국인의 나머지 정리를 공부해 볼까 싶네요..

rdd6584 5년 전 0

대회 참여해주셔서 진심으로 감사합니다.

harinboy님 처음 뵈는 분인데 너무 잘푸셔서 솔직히 놀랐어요.

harinboy 5년 전 1

수학을 더 중점적으로 공부하다가 본격적인 코딩은 비교적 최근에 시작한 편입니다.

이번 네블컵에서 정수론적인(?) 문제가 좀 있어서 특히 재미있게 할 수 있었던 것 같습니다.

칭찬 감사드립니다!

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

문제

문제

출처

ICPC

왜 런타임 에러인지 모르겠습니다ㅠㅠ (C++)

harinboy 5년 전 0

rdd6584 5년 전 0

rdd6584 5년 전 0

chogahui05 5년 전 0

harinboy 5년 전 1

chogahui05 5년 전 0

rdd6584 5년 전 0

harinboy 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말