c++ 회의실 배정 알고리즘(DP 사용)

http://jaimemin.tistory.com/391?category=988050과 비슷한 문제입니다.

두가지 다른 점은 다음과 같습니다.

1. 백준 1931번 문제와 달리 한 회의의 소요시간은 1 이상이고

2. 한 회의의 끝과 그 다음 회의의 시작은 동일할 수 없다는 점입니다.(이런 경우 겹친다고 여긴다.)

물론 탐욕법(greedy method)를 사용하면 쉽게 풀리지만 동적계획법을 연습 중이기 때문에 동적계획법으로도 풀어봤습니다.

/*

회사에 회의실이 하나밖에 없는데, n(<=100)개의 팀이

각각 회의하고 싶은 시간을 그림으로 제출했다.

두 팀이 회의실을 같이 쓸 수는 없기 때문에 이 중 서로 겹치지 않는

회의들만을 골라내서 진행해야 한다. 최대 몇개나 선택 가능할까?

단, i번째 회의의 끝과 i+1번째 회의의 시작은 동일할 수 없다(겹친다고 본다)

단, 하나의 회의는 최소 1 이상 소요

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 101;

 

typedef struct{

        int start, end;

}conference;

 

int N;

conference meeting[MAX];

int cache[MAX];

int before[MAX];

 

bool cmp(const conference a, const conference b) //오름차순

{

        if (a.end == b.end)

        {

               if (a.start < b.start)

                       return true;

        }

        else if (a.end < b.end)

               return true;

        return false;

}

 

void initialize(void)

{

        memset(before, -1, sizeof(before));

        //i번 회의가 시작하기 전에 끝나는 회의들 중 마지막 회의의 번호

        //before[i]에 저장

        for(int i=N; i>0; i--)

               for(int j=i-1; j>0; j--)

                       if (meeting[i].start > meeting[j].end)

                       {

                              before[i] = j;

                              break;

                       }

}

 

int schedule(int idx)

{

        if (idx!=N && (before[idx] == -1 || idx < 1))

               return 1;

        int result = 0;

        //해당 회의를 진행하는 경우와 진행하지 않는 경우

        result += max(schedule(idx - 1), 1 + schedule(before[idx]));

        return result;

}

 

int main(void)

{

        cin >> N;

        meeting[0].start = meeting[0].end = 0;

        for (int i = 1; i <= N; i++)

               cin >> meeting[i].start >> meeting[i].end;

        sort(meeting + 1, meeting + N + 1, cmp);

        initialize();

        cout << schedule(N) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략