글 읽기 - 반례 좀 찾아주세요

zz132456zz 4년 전 0

전 완벽한 코드라고 생각하는데 왜 틀렸다고 하나요?;;

#include<iostream>

using namespace std;

int main() {
	int N;

	cin >> N;

	int arr[10001];

	int X, Y;

	int check = N;

	for (int i = 0; i < N; i++) {
		cin >> X >> Y;
		if (arr[X] == 1) {
			check--;
		}
		for (int j = X; j <= Y; j++) {
			if (arr[j] != 1 && arr[j + 1] == 1) {
				check--;
			}
			arr[j] = 1;
		}
	}

	int result = 0;

	for (int k = 1; k <= 10000; k++) {
		if (arr[k] == 1) {
			result++;
		}
	}

	cout << result - check;
	
}

basekil 4년 전 0

arr[] 선언시 초기화를 안했으니 쓰레기값이 들어가는데 우연히 1이 들어가면 어떻게 될까요

lakshimi 4년 전 0

초기화도 그렇지만, 이 코드로는 통과 못 할겁니다.

일단 색칠하기 알고리즘이 기본인데, 불필요한 코드가 너무 많습니다.

단순하게 생각한다면,

while(n--) {

cin >> x >> y;

for( i = x; i < y; i++) arr[i]=1;

}

만 해도 되죠.

그렇지만, 이 경우 최악의 케이스에서 입력 10,000개에, 10,000번의 for 루프를 돕니다.

그러면 100,000,000번의 arr[i]=1 이란 코드가 실행되어서 시간초과 날 것 같은데요. (짐작이지만요.)

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

문제

문제

출처

ICPC

반례 좀 찾아주세요

zz132456zz 4년 전 0

basekil 4년 전 0

lakshimi 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말