[백준] 19622번 회의실 배정 3 (C++)

https://www.acmicpc.net/problem/19622

 

 

이 문제는 N개의 회의가 존재할때 각각의 회의마다 시작 시간, 끝나는 시간, 회의실의 최대 수용 인원이 주어진다.

 

이때 회의가 겹치지 않게 회의실을 선택하여 최대 수용인원의 개수를 출력하는 문제이다.

 

이때 주어진 문제의 조건에서 임의의 회의 K는 K-1과 K+1이 겹치고 다른 회의와는 겹치지 않는 조건이 존재한다.

 

이 조건을 보지 못해서 문제를 푸는데 시간이 꽤 오래 걸렸다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int N;
vector<tuple<int, int, int>> v;
int dp[100001];

void solve() {
    dp[0] = get<2>(v[0]);
    dp[1] = max(dp[0], get<2>(v[1]));


    for(int i = 2; i < N; i++) {
        dp[i] = max(dp[i-2] + get<2>(v[i]), dp[i-1]);
    }

    cout << dp[N-1];
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({a, b, c});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

dp[0], dp[1]을 먼저 구해놓는다 이후에 현재 보는 회의가 i라고 했을때 i-1과는 겹치기 때문에 i-2와 현재 회의의 수용할 수 있는인원의 합과 이전 회의의 수용값을 비교하여 최댓값으로 갱신해준다.