글 읽기 - 1931번 틀린 부분을 못찾겠습니다 ㅠ

meme0724 6년 전 0

1931번 그리디 알고리즘을 이용해서 나름 생각나는대로 코딩을 해 보았습니다.

회의의 시작 시간과 종료 시간을 각각 pair의 second와 first에 담고 이 시간들의 목록을 담을 vector를 선언했습니다.

그리고 while문 안에서 count로 강의 횟수를 센 다음 최종 count값이 답인 걸로 출력을 하는데

답이 틀렸다고 나오네요.

알고리즘을 구현에는 문제가 없다고 생각하는데 제가 생각하지 못한 다른 경우가 있나요?

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{	
	int i,point,count=1,n;

	scanf("%d", &n);
	vector<pair<int, int>> a(n);

	for(int i=0; i<n; i++)
		scanf("%d %d", &a[i].second, &a[i].first);

	sort( a.begin(), a.end() );
	point=a[0].first;
	i=0;

	while(i<n)
	{
		if(a[i].second >= point)
		{
			point = a[i].first;
			count++;
		}
		i++;
	}

	printf("%d", count);
	return 0;
}

h0ngjun7 6년 전 0

아래 소스는 AC가 나오네요

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int i, point, count = 0, n;

	scanf("%d", &n);
	vector<pair<int, int> > a(n);

	for (int i = 0; i<n; i++)
		scanf("%d %d", &a[i].second, &a[i].first);

	sort(a.begin(), a.end());
	point = -1000000;
	i = 0;

	while (i<n)
	{
		if (a[i].second >= point)
		{
			point = a[i].first;
			count++;
		}
		i++;
	}

	printf("%d", count);
	return 0;
}

h0ngjun7 6년 전 0

만약 입력이

1 1

이면 답을 2출력하시네요

meme0724 6년 전 1

아 감사합니다!!

그런데 1 1이란 테스트케이스도 올바른 입력이라고 할 수 있나요?

1시에 시작해서 1시에 시작하는 회의란 있을 수 없잖아요.

h0ngjun7 6년 전 0

그냥 반례를 찾다보니 그런 게 생각이 나던데..음..

문제에서 아무 조건이 없어서 올바르지 않은 입력은 아니라고 생각되네요....

입력 조건에서 서술이 부족한 것 같습니다.

meme0724 6년 전 0

음 그럴 수도 있겠네요

저는 아무리 봐도 반례가 안 나오던데 도와주셔서 감사합니다!!

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

문제

문제

출처

ICPC

1931번 틀린 부분을 못찾겠습니다 ㅠ

meme0724 6년 전 0

h0ngjun7 6년 전 0

h0ngjun7 6년 전 0

meme0724 6년 전 1

h0ngjun7 6년 전 0

meme0724 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말