글 읽기 - 게시판에 나온 모든 반례를 넣어봤는데 잘 맞습니다.

teang1995 4년 전 0

안녕하세요 선배님들. 도저히 모르겠어서 질문드립니다.

게시판에 나온 반례들을 모두 넣어봤는데 다 맞게 작동했습니다!

제가 아주 기초적인 경우를 고려하지 못 했다는 생각이 드는데, 도저히 제 식견으론 그걸 알아낼 수 없겠어서 질문 드립니다.

아래에 코드가 있습니다. 혹시 간결하지 못한 제 코드가 보기 불편하실까봐, 약간의 주석을 달아두었습니다!

제가 짠 방식은 회의의 끝 시간을 기준으로 오름차순으로, 끝 시간이 같다면 시작 시간을 기준으로 오름차순으로 셸 정렬하였습니다.

그 후, 탐욕법을 이용하여 가장 빨리 끝나는 회의부터 차근차근 넣어서 최대 회의 수를 계산해보았는데 자꾸 틀립니다.

틀린 이유를 잘 모르겠습니다. 알려주시면 너무 감사하겠습니다!

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

int ** arr; //회의 시간 저장 배열

void inc_insertion_sort(int ** arr, int first, int last, int gap);
void shell_sort(int ** arr, int n);
int main()
{
	int N = 0; //회의 수
	int i = 0; //현재 회의 시간
	int j = 1; //다음 회의 시간
	int temp = 0;
	int count = 0;
	scanf("%d", &N);
	arr = (int**)malloc(sizeof(int*) * N);
	for (i = 0; i < N; i++)
	{
		arr[i] = (int*)malloc(sizeof(int) * 2);
	}
	for (i = 0; i < N; i++)
	{
		scanf("%d %d", &arr[i][0], &arr[i][1]);
	}
	shell_sort(arr, N); // 끝나는 시간을 기준으로 오름차순 정렬
	count = 1;          // N이 1 이상이므로 count는 1로 초기화.
	i = 0;
	while (j < N)
	{
		if (arr[j][0] >= arr[i][1])  //뒷 회의의 시작 시간이 앞 회의의 끝 시간 뒤라면
		{
			count++; // count를 1 증가
			i = j;   //현재 회의 시간을 다음 회의시간으로 초기화.
			j++;     //다음 회의 시간 idx++
		}
		else        //j번째 idx의 회의 시작시간이 현재 회의의 끝 시간 보다  빠르다면
		{
			j++;      //다음 회의 시간 idx++
		}
	}
	printf("%d", count);

	return 0;
}

void inc_insertion_sort(int ** arr, int first, int last, int gap)
{
	int i, j, key, temp;
	for (i = first + gap; i <= last; i = i + gap) {
		key = arr[i][1]; 
		temp = arr[i][0];

	
		for (j = i - gap; j >= first && (arr[j][1] > key || (arr[j][1] == arr[i][1]) && arr[j][0] > arr[i][0]); j = j - gap) {
			arr[j + gap][0] = arr[j][0]; 
			arr[j + gap][1] = arr[j][1];
		}

		arr[j + gap][1] = key;
		arr[j + gap][0] = temp;
	}
}

void shell_sort(int ** arr, int n)
{
	int i, gap;

	for (gap = n / 2; gap > 0; gap = gap / 2)
	{
		if ((gap % 2) == 0)
		{
			gap++; // gap을 홀수로 만든다.
		}

		// 부분 리스트의 개수는 gap과 같다.
		for (i = 0; i < gap; i++) {
			// 부분 리스트에 대한 삽입 정렬 수행
			inc_insertion_sort(arr, i, n - 1, gap);
		}
	}
}

yehyun 4년 전 19

반례입니다.

<input>
9 
8 8 
5 8
3 4
2 5 
2 7
8 8
1 10
3 3
10 10

<answer>
6

<output>
5

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

문제

문제

출처

ICPC

게시판에 나온 모든 반례를 넣어봤는데 잘 맞습니다.

teang1995 4년 전 0

yehyun 4년 전 19

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말