글 읽기 - 왜 런타임 에러인지를 모르겠어요

kyu0901 7년 전 0

어느 부분때문에 런타임 에러가 나오는 지를 모르겠어요

/*
 * L.cpp
 *
 *  Created on: 2016. 8. 9.
 *      Author: hyk
 */

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	int N, k, a, cnt;
	vector<int> v;
	vector<int> v2;

	cin >> N;


	for(int i=0; i<N; i++)
	{
		cin >> k;
		v2.push_back(k);
	}

	for(int i=0; i<N; i++)
	{
		a = v2[i];
		for(int j=i; j<N; j++)
		{
			if(j == i)
				v.push_back(a);
			else
			{
				a = a*10 + v2[j];
				v.push_back(a);
			}
		}
	}

	sort(v.begin(), v.end());

	cnt = 0;

	for(int i=0; i<v.size()-1; i++)
	{
		if(v[i]!=v[i+1])
		{
			cnt += 1;
//			cout << v[i] << ' ';
		}
	}

//	cout << v[v.size()-1]<<endl;

	cout << cnt + 1 << endl;

	return 0;
}

yukariko 7년 전 1

2중 for문을 돌면서 v 벡터에 숫자를 채워넣게되는데,

N제한이 10만까지라서 v벡터에 10만 * 10만개를 집어넣게 됩니다.

이는 매우 큰 숫자로 메모리가 부족해지면서 런타임에러가 발생하게 됩니다.

원래는 메모리초과가 발생해야 맞습니다만,

BOJ에서는 너무나 큰 메모리가 초과되게 되면 메모리초과 대신 런타임에러를 반환합니다.

yukariko 7년 전 2

참고로 벡터에 숫자를 집어넣지 않더라도 10만 * 10만의 반복은 시간초과가 발생하게 됩니다.

이 문제는 inch warm 이라는 알고리즘으로 해결할 수 있습니다.

kyu0901 7년 전 0

감사합니다~!

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

문제

문제

출처

ICPC

왜 런타임 에러인지를 모르겠어요

kyu0901 7년 전 0

yukariko 7년 전 1

yukariko 7년 전 2

kyu0901 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말