글 읽기 - 100%에서 오류가 납니다. 어디가 잘못된 걸까요?

ab0061 2년 전 0

오름차순으로 숫자 정렬했습니다.

그 다음에

가장 큰 변 >= 두 번째로 큰 변 + 세 번째로 큰 변

이렇게 되면 삼각형이 만들어지지 않으니, 배열을 한 칸씩 전부 위로 올렸습니다.

어느 부분이 잘못돼서 100%에서 오류가 뜬 걸까요??

#include <stdio.h>

int temp_arr[1000001] = {0};

void merge(int *arr, int start, int middle, int end){
	int i = start;
	int j = middle + 1;
	int k = start;
	
	//비교하여 데이터정렬 및 삽입
	while(i <= middle && j <= end){
		if(arr[i]<=arr[j]) temp_arr[k] = arr[i++];
		else temp_arr[k] = arr[j++];
		k++;
	}
	
	//남은 데이터 삽입
	if(i > middle){
		for(int t = j; t <= end; t++){
			temp_arr[k] = arr[t];
			++k;
		}
	}
	else{
		for(int t = i; t <= middle; t++){
			temp_arr[k] = arr[t];
			k++;
		}
	}
	
	//임시 저장용 배열에 저장된 값을 원래 배열에 넣어줌
	for(int t = start; t <= end; t++){
		arr[t] = temp_arr[t];
	}
}


void mergeSort(int *arr, int start, int end){
	//크기가 1 일 때 까지 호출, 1단위 까지 쪼갬
	if(start < end){
		int middle = (start + end) / 2;
		mergeSort(arr, start, middle);
		mergeSort(arr, middle+1, end);
		//다시 병합
		merge(arr, start, middle, end);
	}
}
int main(){
	
	int i, n;
	int arr[1000001];
    int num = 0;

    scanf("%d", &n);
    for(int l = 0; l < n ; l++) {
    scanf("%d", &arr[l]);
    }

	mergeSort(arr, 0, n - 1);
    n--;
    for(int i = 0; i <= n; i++) {
        if(arr[n] >= arr[n - 1] + arr[n - 2]) {
            n--;
        }
        else{
            num = arr[n] + arr[n - 1] + arr[n - 2];
        }
    }
    if (num == 0) num--;
		printf("%d", num);
	
	return 0;
}

ab0061 2년 전 0

@slah007

댓글 감사합니다.

for문에서 I <= n + 2로 고치거나 i를 2부터 시작해봤는데도 오류가 나는데 이렇게 해결하는게 아닌가요?

slah007 2년 전 1

i <= n+2로 고치면 오히려 더 많은 음수 인덱스 접근이 생깁니다. 실제로 for문의 범위를 어떻게 할 때 n 값이 어디까지 변화하는지 생각해 보세요.

또한 코드에서 어떤 부분의 결과 (ex. 정렬)이 의심스러우면 #include <assert.h>를 넣고 assert(condition);을 하면 condition=false일 때 assertionfailed 런타임 에러를 받아서 쉽게 판정할 수 있습니다.

slah007 2년 전 1

정렬이 틀렸다는 이야기는 아닙니다. 예를 들어 61줄 밑에 assert(n-2>=0);으로 쓸 수 있고 이번 문제가 아니라 다른 문제에도 이렇게 해서 디버깅할 수 있다는 이야기입니다.

예를 들어 공유 소스 보기 (acmicpc.net) 는 assertionfailed를 받고 공유 소스 보기 (acmicpc.net) 는 틀렸습니다를 받는 것으로 보아, 1. 뒤의 코드에서 assert(arr[i-1]<=arr[i])는 성립하므로 정렬에는 문제가 없습니다. 2. 뒤의 코드에서 주석 처리한 부분 assert(n-2>=0); 앞의 코드에서는 런타임 에러를 받으므로 false인 경우가 있다는 것을 알 수 있습니다.

ab0061 2년 전 0

@slah007

감사합니다.

덕분에 n - 2가 0 이하로 떨어지지 않도록 추가해줬더니 맞았습니다.

설명해주신 부분도 꼭 사용해보겠습니다.

정말 감사합니다!

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

문제

문제

출처

ICPC

100%에서 오류가 납니다. 어디가 잘못된 걸까요?

ab0061 2년 전 0

slah007 2년 전 1

ab0061 2년 전 0

slah007 2년 전 1

slah007 2년 전 1

slah007 2년 전 1

ab0061 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말