글 읽기 - [2293번 동전1] 런타임에러 질문드려요!

sukth09 6년 전 0

전역변수로 놓았을 때 런타임에러가 발생하여서 질문게시판을 참고해 동적할당방법으로 해결했습니다.

그런데 질문게시판에 동전의 가치에 대한 범위가 주어지지 않아서 그것 때문에 런타임 에러가 날 수 있단 글을 보았는데요.

이해가 되지 않습니다. 분명 전역변수든 동적할당이든 배열의 최대크기는 K의 최대값인 10001이고 동전의 가치는 제한이 없으니 10001보다 클 수 있단 소리니까요.

그러면 동적할당/전역변수 상관없이 허용하지 않은 인덱스를 접근하는 런타임에러 결과를 도출해야하는 것이 아닌가 해서 질문남깁니다.

아니면 혹 제가 전역변수 배열 선언시 잘못된 부분이 있는 것 인가요?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define CMAX 100
#define PMAX 10000

long N, K;
long coin[CMAX];
long price[PMAX + 1];

long main() {
	long i, j, cnt;
    //int *coin = NULL;
	//int *price = NULL;

	scanf("%d %d", &N, &K);
    //coin = (int *) malloc(sizeof(int) * N);
	//price = (int *) malloc(sizeof(int) * (K + 1));
	//memset(price, 0, K + 1);
	for(i = 0; i < N; i++) {
		scanf("%d", &coin[i]);
	}

	for(i = 0; i <= K; i += coin[0]) {
		if(i) {
			price[i] = 1;
		}
	}

	for(i = 1; i < N; i++) {
		price[coin[i]]++;
		for(j = coin[i] + 1; j <= K; j++) {
			price[j] = price[j] + price[j - coin[i]];
		}
	}
	printf("%d\n", price[K]);
	return 0;
}

채점 환경에서는 제가 아는 바로는 long과 int의 크기가 다릅니다. 채점 환경에서 int는 4바이트고, long은 8바이트로 알고 있습니다. 따라서 long형으로 N개의 공간을 확보하려면 sizeof(long) * N만큼 할당해야지, sizeof(int) * N이라고 하면 원했던 공간의 반밖에 할당을 못 받고, 당연히 인덱스의 큰 쪽 반은 모두 범위를 벗어나게 됩니다.

sukth09 6년 전 0

아 죄송합니다.

아래가 원래 소스였습니다. 근데 런타임에러가 떠서 long으로 한번 바꿔본 것입니다.

근데 문제에서 답인 경우의 수는 2^31을 넘지 않는다고 해서 int로 작성하였습니다.

#include <stdio.h>

#define CMAX 100
#define PMAX 10000

int N, K;
int coin[CMAX];
int price[PMAX + 1];

int main() {
	int i, j, cnt;

	scanf("%d %d", &N, &K);
	for(i = 0; i < N; i++) {
		scanf("%d", &coin[i]);
	}

	for(i = 0; i <= K; i += coin[0]) {
		if(i) {
			price[i] = 1;
		}
	}

	for(i = 1; i < N; i++) {
		price[coin[i]]++;
		for(j = coin[i] + 1; j <= K; j++) {
			price[j] = price[j] + price[j - coin[i]];
		}
	}
	printf("%d\n", price[K]);
	return 0;
}

djm03178 6년 전 1

주석 치신 부분이 정답을 받은 온전한 코드인지는 모르겠지만, 만약 그렇다면 저는 "운이 좋았다"고 생각되네요.

배열의 인덱스를 벗어났다고 해서 무조건 바로 segmentation fault가 되는 것은 아닙니다. 우연히도 그 벗어난 메모리 위치가 이 프로그램에게 할당된 곳일 수도 있으니까요. 다만 전역으로 선언했을 땐 그 공간이 건드리면 안 되는 곳이었고, 동적 할당을 했을 때는 '우연히' 접근해도 되는 공간이 아니었나 생각이 됩니다.

확실히 40%에서 동전 중에 가치가 최소 2만이 넘는 게 들어오기는 하네요.

sukth09 6년 전 0

답변 감사합니다. 메모리에 대한 확실한 개념이 없어서 이해가 안됐던 부분이네요.

혹시 40%에서 가치가 최소 2만이 넘는 것을 아시는건 테스트케이스를 가지고 계신건가요!?

그리고 본 소스가 정답을 맞은 소스입니다!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int N, K;

int main() {
	int i, j, cnt;
	int *coin = NULL;
	int *price = NULL;

	scanf("%d %d", &N, &K);
	coin = (int *) malloc(sizeof(int) * N);
	price = (int *) malloc(sizeof(int) * (K + 1));
	memset(price, 0, K + 1);
	for(i = 0; i < N; i++) {
		scanf("%d", &coin[i]);
	}

	for(i = 0; i <= K; i += coin[0]) {
		if(i) {
			price[i] = 1;
		}
	}

	for(i = 1; i < N; i++) {
		price[coin[i]]++;
		for(j = coin[i] + 1; j <= K; j++) {
			price[j] = price[j] + price[j - coin[i]];
		}
	}
	printf("%d\n", price[K]);
	return 0;
}

djm03178 6년 전 1

케이스를 가지고 있는 건 아니고, if (coin[i] > 20000) while (1); 이라는 걸 넣고 시간 초과가 나는 것을 확인했을 뿐입니다.

sukth09 6년 전 0

정보 감사합니다. 많은 도움이 됐습니다!

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

문제

문제

출처

ICPC

[2293번 동전1] 런타임에러 질문드려요!

sukth09 6년 전 0

djm03178 6년 전 1

sukth09 6년 전 0

djm03178 6년 전 1

sukth09 6년 전 0

djm03178 6년 전 1

sukth09 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말