프로그래밍

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

[난이도] Silver2
[유형] DP

[풀이]
희이실 배정 2 문제와 다르게 N 제한이 100000으로 늘어났기 때문에 단순 브루트포스로는 풀 수 없습니다.
DP를 이용하면 쉽게 해결할 수 있습니다.
회의 K가 K-1,K+1 회의와 시간이 무조건 겹친다는 조건을 이용하면
회의 i를 선택한 경우와 선택하지 않은 경우를 나누는 점화식을 세울 수 있습니다.

DP[i] (sol(i)) : i~N-1번 회의중에 임의의 회의를 선택했을 때, 최대 인원의 수

1) i를 선택한 경우, i+1을 선택할 수 없으므로
   c[i]+sol(i+2)

2) i를 선택하지 않은 경우,
    sol(i+1)

sol(i) = max(c[i]+sol(i+2), sol(i+1))

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,a[100001],b[100001],c[100001],dp[100001];
int sol(int n){
    if(n>=N) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    return ret=max(c[n]+sol(n+2),sol(n+1));
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/19622.cpp