글 읽기 - 런타임 에러 질문 드립니다.

adfsfsf 5년 전 0

약수 목록 중, a의 n제곱 형태의 약수만을 모아서 전부 곱하는 형태로 알고리즘을 짰습니다.

진짜 약수의 목록을 정렬한다.
진짜 약수들을 작은 수부터 차례대로 소수 목록과 비교한다.

2.1. 만약 소수 목록의 현재 비교 대상이 없으면

2.1.1. 만약 현재 검사 중인 진짜 약수가 특정 소수의 제곱수 형태였다면 소수의 제곱수를 모아놓은 배열을 갱신한다.

2.1.2. 이외에는 소수 목록에 새로운 수를 추가하고, 해당 인덱스에 대응하는 제곱수 배열에 해당 소수를 추가한다.

2.2. 만약 현재 점검 중인 진짜 약수가 소수 목록의 비교 대상으로 나누어 떨어지면

2.2.1. 만약 이전에 또다른 소수로 나누어 떨어졌었다면 다음 진짜약수를 비교하기 시작한다.

2.2.2. 이외에는 현재 인덱스를 저장해 둔다.

3. 지금껏 저장한 제곱수들을 모두 곱한다.

4. 곱한 결과가 진짜 약수 중 가장 큰 값과 같다면 2를 곱한 값을, 아니면 결과를 그냥 출력한다.

32비트가 int형 정수 크기라면, 이 알고리즘대로면 int형을 그대로 써도 큰 문제가 없지 않나요?

#include <iostream>
#include <algorithm>
using  namespace std;
int main(void)
{
	int *a, *b, *c;//a : 진짜 약수를 저장할 배열, b : 소수 배열, c : 소수의 제곱수 저장 배열
	int N, p = -1, result;
	cin >> N;
	int i;
	a = new int[N];
	b = new int[N];
	c = new int[N];
	for (i = 0; i < N; i++)
	{
		cin >> a[i];
		b[i] = 0;
		c[i] = 0;
	}
	b[i] = 0;
	c[i] = 0;
	sort(a, a + N);
	for (i = 0; i < N; i++)//N개의 진짜 약수에 대하여
	{
		for (int j = 0;; j++)//소수 목록에 대하여
		{
			if (b[j] == 0)//만약 비어있다면(현재 점검 중인 인덱스가)
			{
				if (p != -1)//현재 점검 중인 진짜 약수가 이미 찾아낸 어떤 소수로 나누어 떨어졌다면
				{
					c[p] = a[i];//해당 소수에 대한 제곱수의 최댓값 갱신
					p = -1;
					break;
				}
				else//아니면 목록 추가
				{
					b[j] = a[i];
					c[j] = a[i];
					break;
				}
			}
			if (a[i] % b[j] == 0)//진짜 약수가 현재 확인 중인 소수로 나누어 떨어진다면
			{
				if (p != -1)//이미 다른 소수로도 나누어 떨어졌다면 다음 진짜 약수로 넘어간다.
				{
					p = -1;
					break;
				}
				else//이외에는 현재 인덱스를 저장한다.
					p = j;
			}
		}
	}
	result = c[0];
	for (i = 1;; i++)//결과는 모든 제곱수를 곱한 값
	{
		if (c[i] != 0)
			result *= c[i];
		else
			break;
	}
	if (result == a[N - 1])//결과가 진짜 약수의 최댓값과 같으면 2를 곱한 값을 출력
		cout << result * 2 << endl;
	else//아니면 그냥 출력
		cout << result << endl;
	return 0;
}

bupjae 5년 전 0

13번째 줄의 loop 를 끝내고 나면 i = N 이 됩니다. 그렇게 되면 19번째와 20번째 줄에서 0~N-1 까지 준비된 배열에서 N번째 방에 값을 쓰게 됩니다. 런타임 에러의 원인은 이것 때문일 가능성이 높습니다.

두 줄을 고친다고 해도 사용하고 있는 알고리즘은 잘못된 알고리즘입니다.

다음 입력에 대해서

정답: 999966000289

오답: 1999966

1
999983

adfsfsf 5년 전 0

@bupjae

아, 그렇군요. 곱셈 결과가 진짜 약수 중 가장 큰 것과 같으면 진짜 약수 중 가장 작은 소수와 곱한 것을 출력해야 하는군요. 감사합니다.

adfsfsf 5년 전 0

@bupjae

언급해주신 부분과 62번 줄을 수정하여서 AC를 받았습니다. 감사합니다.

#include <iostream>
#include <algorithm>
using  namespace std;
int main(void)
{
	int *a, *b, *c;//a : 진짜 약수를 저장할 배열, b : 소수 배열, c : 소수의 제곱수 저장 배열
	int N, p = -1, result;
	cin >> N;
	int i;
	a = new int[N];
	b = new int[N + 5];//배열 크기를 충분히 함.
	c = new int[N + 5];//배열 크기를 충분히 함.
	for (i = 0; i < N; i++)
	{
		cin >> a[i];
		b[i] = 0;
		c[i] = 0;
	}
	b[i] = 0;
	c[i] = 0;
	sort(a, a + N);
	for (i = 0; i < N; i++)//N개의 진짜 약수에 대하여
	{
		for (int j = 0;; j++)//소수 목록에 대하여
		{
			if (b[j] == 0)//만약 비어있다면(현재 점검 중인 인덱스가)
			{
				if (p != -1)//현재 점검 중인 진짜 약수가 이미 찾아낸 어떤 소수로 나누어 떨어졌다면
				{
					c[p] = a[i];//해당 소수에 대한 제곱수의 최댓값 갱신
					p = -1;
					break;
				}
				else//아니면 목록 추가
				{
					b[j] = a[i];
					c[j] = a[i];
					break;
				}
			}
			if (a[i] % b[j] == 0)//진짜 약수가 현재 확인 중인 소수로 나누어 떨어진다면
			{
				if (p != -1)//이미 다른 소수로도 나누어 떨어졌다면 다음 진짜 약수로 넘어간다.
				{
					p = -1;
					break;
				}
				else//이외에는 현재 인덱스를 저장한다.
					p = j;
			}
		}
	}
	result = c[0];
	for (i = 1;; i++)//결과는 모든 제곱수를 곱한 값
	{
		if (c[i] != 0)
			result *= c[i];
		else
			break;
	}
	if (result == a[N - 1])//결과가 진짜 약수의 최댓값과 같으면 가장 작은 소수값인 진짜 약수를 곱한 값을 출력
		cout << result * b[0] << endl;
	else//아니면 그냥 출력
		cout << result << endl;
	return 0;
}

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

문제

문제

출처

ICPC

런타임 에러 질문 드립니다.

adfsfsf 5년 전 0

bupjae 5년 전 0

adfsfsf 5년 전 0

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말