문제 정의

회의들 각각의 시작 시간, 끝나는 시간, 회의 인원이 주어질 때, 한 개의 회의실에서 회의를 진행할 수 있는 최대 인원을 구하라.

제한 : 임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.

아이디어

문제를 해결하는데 핵심이 되는 조건은, 임의의 회의는 앞뒤의 회의와 무조건 겹치고, 다른 회의들과는 겹치지 않는다는 조건이다. 이 조건이 없다면 고려해야 할 것이 많아지겠지만, 이 조건으로 인해 어떤 회의 K를 선택할 지 아니면 앞의 K - 1 회의를 선택할 지 결정하는 문제로 간단하게 해결할 수 있다.

다이나믹 프로그래밍 기법을 사용하여, D[n]를 1 ~ n번 회의 중에서 n번 회의를 선택할 때 최대 회의 인원으로 설정한다. 그렇다면 D[n]의 값은 (n - 2번 회의를 선택한 경우, n - 3번 회의를 선택한 경우) 둘 중 큰 값 + n번 회의의 인원으로 구한다.

n번 회의를 선택할 때 n - 1번 회의는 겹치므로 선택할 수 없다. 그러므로 바로 이전에 선택할 수 있는 n - 2번 회의를 선택하거나, 한 칸 건너뛰고 n - 3번 회의를 선택하거나, 두 경우 중 더 큰 회의 인원을 가진 경우를 선택하면 된다. 회의 인원은 자연수이므로, n - 2번 회의와 n - 3번 회의 모두를 건너뛰는 것보다 n - 2번 회의를 선택하는 경우가 무조건 크다. 그러므로 n - 2번과 n - 3번 회의 모두 건너뛰는 경우는 답이 되지 않는다.

그러므로 D[n] = (D[n - 3] < D[n - 2]) ? D[n - 2] + people[n] : D[n - 3] + people[n] 으로 D를 채운다.

최대 회의 인원을 갖는 경우가 마지막 회의를 포함할 수도 있고, 아니고 마지막 전 회의를 포함할 수도 있으므로 D[N -1] 과 D[N -2] 둘 중 큰 값이 정답이 된다.

풀이

먼저 회의 인원을 입력받아 people 배열에 저장한다. 제한 조건에 의해 앞뒤 회의는 무조건 겹치고, 나머지는 안 겹치므로, 회의 시작 시간과 종료 시간은 버린다.

반복문에서 D[n - 3] 에 접근하므로, D[0] ~ D[2] 까지 직접 채워준다. (N = 1, 2 예외 처리가 필요하다.)

n = 3 부터 n = N - 1 까지 0번 ~ n번까지 중 n번 회의를 선택할 때 최대 인원 D[n] 을 채운다.

D[N - 1] 과 D[N - 2] 둘 중 큰 값을 정답으로 출력한다. (N = 1, 2 예외 처리가 필요하다.)

코드

#include <iostream>
using namespace std;

int N, temp;
int people[25];
int D[25];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    for (int n = 0; n < N; n++) {
        cin >> temp >> temp >> people[n];
    }

    D[0] = people[0];
    if (1 < N) D[1] = people[1];
    if (2 < N) D[2] = D[0] + people[2];

    for (int n = 3; n < N; n++) {
        D[n] = (D[n - 3] < D[n - 2]) ? D[n - 2] + people[n] :
                                       D[n - 3] + people[n];
    }

    if (N == 1)
        cout << D[0] << '\n';
    else if (N == 2)
        cout << ((D[0] < D[1]) ? D[1] : D[0]) << '\n';
    else
        cout << ((D[N - 2] < D[N - 1]) ? D[N - 1] : D[N - 2]) << '\n';
    return 0;
}

결과