[백준 19621번] 회의실 배정 2 (C++)

문제링크 : https://www.acmicpc.net/problem/19621

19621번: 회의실 배정 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, s[26], e[26], n[26];
int result;

void func(int idx, int sum)
{
    if(idx >= N)
    {
        result = max(result, sum);
        return;
    }

    func(idx + 1, sum); //현재 값 스킵
    func(idx + 2, sum + n[idx]); //현재 값 선택
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> s[i] >> e[i] >> n[i];
    }

    func(0, 0);

    cout << result;
    return 0;
}

 

문제에 조건 중 "임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다." 이 존재한다.

 

따라서 현재 값을 선택한 경우와 스킵한 경우를 고려해야한다.

현재 값을 선택한 경우면 합에 현재 값을 더하고, 다음 회의는 불가능하기에 다다음 회의를 선택한다. (idx + 2)

현재재 값을 스킵한 경우라면 합은 그대로 넘겨주고, 다음 회의가 가능하기에 다음 회의를 선택한다. (idx + 1)

 

이렇게 더한 idx 의 값이 N과 같거나 커지면 더 이상 탐색이 불가능하게 된다.

따라서 최대 합을 저장하고 탐색을 종료한다.