글 읽기 - 이 문제 하나로 10시간은 고민한것같습니다..도와주시면 감사하겠습니다..ㅠㅠㅠ

wnsgur1595 4년 전 0

UCPC 2019 예선 C번문제인데, 그리디 알고리즘으로 풀려고 했어요.

일단, ms와 ms2라는 멀티셋 2개를 만들었고, ms는 모든 대회가 일찍 끝나는 순으로 정렬된 멀티셋이고, ms2는 K-1명이 마지막으로 참가한 대회의 끝나는 날(K-1개)들을 저장해놨습니다. 그래서, 처음에는 ms에서 맨앞부터 K-1개를 꺼내어 ms2에 끝나는날 K-1개를 채워넣구요. 그 다음부터는 형섭이가 끝나는날을 보면서 형섭이가 끝나는날 이전에 시작하는 대회는 ms에서 하나씩 삭제해나가고, 만약 형섭이가 대회에 참가할 수 있다면, 먼저 ms2의 K-1명도 참여할 수 있는지 먼저 확인한 후에, 참여할 수 있는 사람들 중 가장 마지막에 끝난 사람이 새로운 대회에 참가하도록 하였습니다.

제 코드에서 어떤 부분이 잘못된 걸까요..?

#include<iostream>
#include<set>
#include<algorithm>

using namespace std;

int N, K, ce;

struct Node {
	int s = 0;
	int e = 0;
};

multiset<Node> ms;
multiset<int> ms2;

bool operator<(Node a, Node b) { // ms를 일찍 끝나는 순으로 정렬하기 위한 operator
	if (a.e < b.e) {
		return true;
	}
	else if (a.e > b.e) {
		return false;
	}
	else {
		if (a.s < b.s) return true;
		else return false;
	}
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		Node t;
		cin >> t.s >> t.e;
		// ms에 모든 대회를 넣는다. ( 일찍 끝나는 순으로 정렬 )
		ms.insert(t);
	}

	if (K - 1 >= N) { // 만약 대회수보다 내 등수가 낮으면 참가할 수 있는 대회가 없으니 0 출력
		cout << 0 << endl;
		return 0;
	}

	for (int i = 0; i < K - 1; i++) {	// 가장 일찍 끝나는 대회 K-1개를 ms2에 저장한다. ( K-1명이 이 대회들을 참가했다고 판단 )
										// ms2에는 각 대회가 끝나는 날을 저장한다.
		multiset<Node>::iterator it = ms.begin();
		ms2.insert((*it).e);
		ms.erase(it);
	}
	int Count = 0;
	for (int i = K - 1; i < N; i++) {
		multiset<Node>::iterator it = ms.begin();
		if (ce < (*it).s) {				// ms의 맨 앞꺼의 시작일을 봐서 만약 형섭이가 이 대회를 참가할 수 있다면, if문 안으로 들어간다.
			multiset<int>::iterator it2 = ms2.lower_bound((*it).s);
			if (it2 == ms2.begin()) {	// 만약 K-1명중 이 대회를 참가할 수 있는 사람이 없다면, 형섭이가 참가하므로, 형섭이의 대회가 끝나는 날은 (*it).e이고, 형섭이가 우승한 대회++
				ce = (*it).e;
				Count++;
			}
			else {						// 만약 K-1명중 이 대회를 참가할 수 있는 사람이 있다면, 형섭이 대신 그 사람이 참가하며, 이 때 대회에 참가하는 사람은 이 대회에 참가할 수 있는 사람들 중 가장 늦게 끝난 사람이다.
				it2--;
				ms2.erase(it2);
				ms2.insert((*it).e);
			}
		}
		ms.erase(it);
	}

	cout << Count << endl;

	return 0;
}

evenharder 4년 전 2

'가장 일찍 끝나는 대회 K-1개를 ms2에 저장한다.' 부분이 틀렸습니다.

가장 먼저 일찍 끝나는 K-1개의 대회들을 형섭이가 참가할 수 없는 건 맞지만, 경우에 따라서 K-1명보다 적은 인원으로도 이 대회들을 참가할 수 있기 때문입니다.

다음은 반례입니다.

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

예제 출력
0

현재 출력
1

설명
  1 2 3 4 5 6 7 8
1   o---o o-o
2     o-------o
3 o-------------o

다음과 같이 대회를 참가하면 4등인 형섭이는 참가할 수 있는 대회가 없습니다.
그러나 현재 알고리즘은 3번째 대회까지 3명을 이용하고, 이 경우 마지막 대회에 참가할 수 있는 사람이 없게 됩니다.

wnsgur1595 4년 전 0

감사합니다ㅠㅠㅠ 전혀 생각하지 못한 곳에서 논리오류가 있었네요! 감사합니다ㅠㅠ

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

문제

문제

출처

ICPC

이 문제 하나로 10시간은 고민한것같습니다..도와주시면 감사하겠습니다..ㅠㅠㅠ

wnsgur1595 4년 전 0

evenharder 4년 전 2

wnsgur1595 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말