[문제해결기법] 프로그램편성

프로그램의 시작 시간과 끝시간을 준다. (시간&분으로 주지 않고 분으로 합쳐서 준다)

중간에 광고가 있을 수도 있고 없을 수도 있다. 

("전 프로그램의 끝시간과 이후 프로그램의 시작시간이 똑같지 않아도 된다"는 의미이다.)

최대 끝시간은 1000분이다. (0<=Time<=1000)

0분부터 1000분까지 프로그램을 최대 몇개까지 넣을 수 있을까?

이 문제는 끝시간이 가장 빠른 순서대로 프로그램을 넣으면 프로그램의 수가 최대가 된다. 

stl의 priority_queue를 이용하면 쉽게 정렬이 가능하고

queue에 들어간 모든 값이 pop되었을 때 함수를 끝내면 된다.

#include <iostream> #include <queue> #include <vector> #include <fstream> #include <algorithm> #include <functional> using namespace std; #define X pair<int,int> //앞의 int는 끝나는 시간 뒤의 int는 시작시간 -> priority_queue는 앞의 int를 기준으로 정렬하기 때문에 priority_queue<X, vector<X>, greater<X>> time_list; //pair<end_time,start_time> int result; /* 이 문제의 관건은 마지막 시간이 제일 짧은 것부터 나온다는 것이다. 그래서 priority_queue를 사용했다. */ void check_time() { int before_end_time = 0; //이전에 끝났던 시간 -> 만약 시작시간이 이전에 끝났던 시간보다 앞선다면 스케쥴표에 넣을 수 없다. while (!time_list.empty()) { int start_time = time_list.top().second, end_time = time_list.top().first; //queue에 남아있는 끝나는 시간 스케쥴중 가장 빠른걸 가지고 나온다. time_list.pop(); if (before_end_time > start_time) continue; //만약 시작시간이 이전에 끝났던 시간보다 앞선다면 스케쥴표에 넣을 수 없다. if (1000 < end_time) break; //1000까지만 방송하기로 했으므로! result++; //어짜피 예외처리는 앞에서 했으니까 여기까지 왔으면 맞는거다! before_end_time = end_time; //그리고 이전의 끝시간을 새로 들어온 스케쥴의 끝시간으로 교체한다. } } int main() { ifstream fcin; fcin.open("A_input.txt"); ifstream fcout; fcout.open("A_output.txt"); int for_count; fcin >> for_count; while (for_count--) { int max_time, program_count,start_time,end_time; fcin >> max_time>>program_count; while (program_count--) { fcin >> start_time >> end_time; time_list.push(make_pair(end_time, start_time)); } result = 0; check_time(); int answer = 0; fcout >> answer; if(answer!=result) cout << "wrong" << endl; } cout << "perfect" << endl; system("pause"); }