[BOJ/백준][Gold3] 19623 : 회의실 배정 4 (C++)

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

19623번: 회의실 배정 4

 

 

[난이도] Gold3
[유형] DP

[풀이]
l,r,v (시작시간,종료시간,참여인원수)를 저장하는 구조체 P 배열을 선언한 뒤,
시작시간을 기준으로 정렬해줍니다.

그 뒤, lower_bound 사용을 위해 l에 대한 배열 s를 선언하여 따로 저장해줍니다.

DP[i] (sol(i))  : i~N-1 회의가 남았을 때, 회의를 진행할 수 있는 최대 인원

1) 회의 n를 선택 안한 경우
    sol(n+1) (n+1~N-1 회의가 남았을 때, 회의를 진행할 수 있는 최대 인원)

2) 회의 n를 선택한 경우,
    회의 n의 종료 시간보다 시작이 늦는 회의부터 선택할 수 있으므로
    lower_bound(s+n,s+N,a[n].r)-s; 와 같이 lower_bound를 이용하여
    회의 n의 종료시간보다 회의 시작이 늦는 가장 빠른 회의 i를 찾아 주면 됩니다.
    그러면 식은
    (회의 n에 참여하는 사람 수) + sol(i) 이 됩니다.

1,2의 max 값이 sol(i)의 값이 됩니다.

 

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct P{
    int l,r,v;
};
int N,dp[100001],s[100001];
P a[100001];
bool cmp(P& p,P& q){
    return p.l < q.l;
}
int sol(int n){
    if(n>=N) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    int i = lower_bound(s+n,s+N,a[n].r)-s;
    ret = max(sol(n+1),a[n].v+sol(i));
    return ret;
}
int main(){
    scanf("%d",&N);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].v);
    sort(a,a+N,cmp);
    for(int i=0;i<N;i++) s[i] = a[i].l;
    printf("%d",sol(0));
}

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