글 읽기 - C++ 그리디/정렬문제 질문 드립니다.(문제 1931)

kcsoo1234 2년 전 0

정말 질문을 안하려고 했으나...머리가 굳은 관계로 질문 드립니다...

처음에 선택 정렬을 사용해서 문제를 풀었는데 시간 초과가 나와서 합병 정렬로 바꾼 코드입니다.

예시 답은 똑같이 나오는데 항상 채점 80~90% 에서 틀렸다고 오류가 뜹니다...

틀린 부분을 찾을 수 없어서 이렇게 질문 드립니다 ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

typedef struct meeting {
	int start;
	int end;
	int gap;
}meeting;

meeting sorted[100001];

void merge(meeting a[], int m, int mid, int n) {
	int i = m;
	int j = mid + 1;
	int k = m;
	while (i <= mid && j <= n) {
		if (a[i].end <= a[j].end) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
	if (i > mid) {
		for (int t = j;t <= n;t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else {
		for (int t = i;t <= mid;t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	for (int i = m;i <= n;i++) {
		a[i] = sorted[i];
	}
}

void mergesort(meeting a[], int left, int right) {
	int mid;
	if (left == right) {
		return;
	}
	mid = (left + right) / 2;
	mergesort(a, left, mid);
	mergesort(a, mid + 1, right);
	merge(a, left, mid, right);
}

int main() {

	int N, s, e, cnt=0;
	meeting *M;
	meeting nowM;

	cin >> N;

	M = (meeting*)malloc(sizeof(meeting) * N);

	for (int i = 0;i < N;i++) {
		cin >> s >> e;
		M[i].start = s;
		M[i].end = e;
		M[i].gap = e - s;
	}

	mergesort(M, 0, N - 1);

	nowM = M[0];
	cnt++;

	for (int i = 1;i < N;i++) {
		if (nowM.end <= M[i].start) {
			nowM = M[i];
			cnt++;
		}
	}

	cout << cnt;

	free(M);

	return 0;
}

g072923 2년 전 1

끝나는 시간이 같으면 시작하는 시간 시간이 빠른 순으로 정렬해주어야합니다

그래야지

7 7

4 7

같은 경우에도 세줄수 있습니다

kcsoo1234 2년 전 0

와 진짜 감사합니다. 생각도 못한 케이스네요ㅎ... 덕분에 해결했습니다!

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

문제

문제

출처

ICPC

C++ 그리디/정렬문제 질문 드립니다.(문제 1931)

kcsoo1234 2년 전 0

g072923 2년 전 1

kcsoo1234 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말