글 읽기 - 예제는 일단 맞게 뜨는데 어디가 틀렸는지 모르겠습니다....

elixter 5년 전 0

여러가지를 해봤는데 다 답은 맞게나오는 것 같습니다만... 혹시 예외가 어떤게 있을까요????

#include <iostream>
#include <algorithm>

using namespace std;

class Node {
public:
	int start;				// Conference start time
	int end;				// Conference end time
	int duration;
public:
	Node() : start(0), end(0), duration(0) {}		// Default constructor
public:
	bool operator<(Node &a) {
		if (start < a.start) return true;
		else if (start == a.start && duration < a.duration) return true;
		else return false;
	}
};

int roomAllocate(int n, Node confs[]);

int main() {
	int N;			// # of Conference
	cin >> N;

	Node * conf = new Node[N + 1];

	// input data
	for (int i = 1; i <= N; i++) {
		cin >> conf[i].start;
		cin >> conf[i].end;
		conf[i].duration = conf[i].end - conf[i].start;
	}

	sort(conf, conf + N);		// sorting increasing order



	cout << roomAllocate(N, conf);

	return 0;
}

int roomAllocate(int n, Node confs[]) {
	int *DP = new int[n + 1];				// DP[i] is number of conference can be allocated when serch i th confernce
	int i;
	int alloc = 0;
	DP[0] = 0;


	// if i th conference start time is before previous selected conference, check next conference
	// else compare i th conference's end time and i + 1th start time
	// if i th conference's end time is after i + 1 th start time
	// compare duration and select short one.

	for (i = 1; i <= n; i++) {
		if (i == n) {
			if (confs[DP[i - 1]].end > confs[i].start) DP[i] = DP[i - 1];
			else {
				DP[i] = i;
				alloc++;
			}
		}
		else {
			if (confs[DP[i - 1]].end > confs[i].start) DP[i] = DP[i - 1];
			else {
				if (confs[i].end <= confs[i + 1].start) {
					DP[i] = i;
					alloc++;
				}
				else {
					if (confs[i].duration <= confs[i + 1].duration) {
						DP[i] = i;
						alloc++;
					}
					else DP[i] = DP[i - 1];
				}
			}
		}
	}

	return alloc;
}

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

문제

문제

출처

ICPC

예제는 일단 맞게 뜨는데 어디가 틀렸는지 모르겠습니다....

elixter 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말