글 읽기 - ucpc 예선 문제 c번 (대회) 어디가 틀렸을까요?

leo5469 4년 전 0

끝나는날 기준으로 대회를 돌면서 막을수 있는건 모두 막게끔 구현을 했는데 제가 생각하는 예제는 모두 맞게 나오는데 답은 틀렸다고 나오네요.

ucpc 예선 공식 풀이에선 segment tree를 이용한다고 하는데 꼭 그렇게 해야하는지, 그렇다면 제 구현은 뭐가 틀렸고 왜 꼭 segment tree를 써야하는지 알려주시면 감사하겠습니다 고수님덜 ㅠㅠ.

풀이 링크

https://drive.google.com/file/d/1lEkJ4sW5s2bD8SXHh2nYVp8MgXf2nkNg/view

#include <iostream>
#include <algorithm>

using namespace std;

int N, K;
struct se
{
	int s, e;
	bool operator<(se &u)
	{
		// e기준 오름차순 true면 냅둠
		if (this->e < u.e) return true;
		else if (this->e == u.e) return this->s < u.s;
		return false;
	}
};
// 대회 일정 저장
se con[100000];
// 1~K등 까지의 끝나는 날 저장
int es[100001];

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		int s, e;
		cin >> s >> e;
		con[i] = { s, e };
	}
    // 끝나는날 기준 오름차순 정렬
	sort(con, con + N);

	int ans = 0;
	int k = 1;
	int ke = 0;
    // 대회를 돌면서 1~K-1등이 막을 수 있을 때까지 막음
	for (int i = 0; i < N; i++)
	{
        // 형섭이가 참가한 대회와 겹치는 대회는 무시
		if (ke >= con[i].s) continue;
        
        // 이 대회를 형섭이가 나가지 못하게 막을 수 있는 사람이 있는지 체크
		for (int tk = 1; tk <= K; tk++)
		{
            // 있다면 해당 사람을 기억
			if (es[tk] < con[i].s)
			{
				k = tk;
				break;
			}
		}
        // 막을 수 있는 사람이 참가한 대회가 끝나는 날을 기록
		es[k] = con[i].e;

        // 결국 막지 못했다면 이후 형섭이가 마지막으로 참가한 대회와 겹치는 대회는 모두 무시하기 위해
        // 해당 대회의 끝나는 날을 ke 변수에 기록
		if (k == K)
		{
			ans++;
			ke = con[i].e;
		}
	}
	cout << ans << endl;

	return 0;
}

evenharder 4년 전 3

45번째 줄 밑으로 진행되는 로직이 시간 복잡도 상으로도, 알고리즘 측면에서도 문제입니다.

시간 복잡도상으로는 최악의 경우 O(NK)일 수 있기 때문에, 시간 초과를 면치 못합니다. 때문에 C++의 경우 std::set 등의 자료구조 사용이 필요할 수 있습니다.

알고리즘 측면에서는, es[tk] < con[i].s인 사람 중 es[tk]가 최대인 사람을 뽑아야 합니다. 이건 반례를 보시는 게 좋을 것 같습니다.

예제 입력
4 3
1 2
2 4
5 6
3 7

예제 입력
0

설명
1번째와 4번째 대회를 1등이, 2번째와 3번째 대회를 2등이 나가면 3등인 형섭이가 이길 수 없다.

evenharder 4년 전 2

'예제 출력'이 '예제 입력'으로 오타가 났습니다. 참고해주세요.

leo5469 4년 전 0

우와 진짜 감사합니다! ㅠㅠ

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

문제

문제

출처

ICPC

ucpc 예선 문제 c번 (대회) 어디가 틀렸을까요?

leo5469 4년 전 0

evenharder 4년 전 3

evenharder 4년 전 2

leo5469 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말