엘리스 코드 챌린지 Day 8 강림제

문제

 

풀이

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

이 문제와 같은 풀이입니다.

 

엘리스는 강림제에 참여한 신도들이 T명 이상 모여야 지상에 강림한다고 합니다.

만약 신도들이 T명 미만으로 모였을 때 친구를 최대 K명까지 초대하여 T명을 맞출 수도 있습니다.

친구들은 친구들을 제외한 신도들이 T명 이상이 되었다면 모두 탈출한다고 하여 적절한 시기에만 친구를 불러야 합니다.

 

저는 dp로 문제에 접근했고, 우선 누적합을 통해 참여하는 신도들의 수를 시간별로 구합니다.

범위로 누적합을 구해야하기 때문에 imos 기법을 활용했습니다.

imos 기법으로 범위의 양 끝지점에만 카운팅을 먼저 하고, 마지막에 한번에 누적합을 구할 수 있습니다.

 

dp[N][K][pre]: N 시간에 친구 K명을 부를 수 있고, 이미 참여중인 친구가 pre명일 때 엘리스가 지상으로 강림하는 최대 시간

문제에서 나올 수 있는 경우는 4가지입니다.

1. 신도들만 T명 이상 모였을 경우

2. 신도 + 이미 참여중인 친구들이 T명 이상 모였을 경우

3. 친구들을 더 추가하여 T명을 채울 수 있는 경우

4. 친구들을 추가해도 T명을 채우지 못하는 경우

 

1번의 경우는 엘리스가 강림할 수 있으므로 +1을 하고 다음 시간을 확인합니다.

이미 참여중인 친구들이 있다면 모두 탈출하기 때문에 pre는 0으로 맞춥니다.

 

2번의 경우도 엘리스가 강림할 수 있으므로 +1을 하고 다음 시간을 확인합니다.

친구들을 제외한 시도들이 T보다 적으므로 pre도 그대로 유지합니다.

 

3번의 경우도 엘리스가 강림할 수 있으므로 +1을 하고 다음 시간을 확인합니다.

친구를 tmp명 더 추가합니다. pre는 pre + tmp가 되겠고, k에서도 tmp만큼 빼줍니다.

 

4번의 경우는 엘리스가 강림할 수 없으므로 바로 다음 시간을 확인합니다.

이때 친구들을 더 추가하지 않으며, 이미 참여중인 친구들은 계속 참여하기 때문에 pre를 그대로 유지합니다.

 

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 310
using namespace std;
 
int sum[MAX];
int dp[MAX][MAX][MAX];
int N, M, K, T;
 
int solve(int idx, int k, int pre) {
    if (idx > N) return 0;
    int& ret = dp[idx][k][pre];
    if (ret != -1) return ret;
 
    if (sum[idx] + pre >= T) {
        int next = pre;
        if (sum[idx] >= T) next = 0;
        return ret = solve(idx + 1, k, next) + 1;
    }
 
    ret = solve(idx + 1, k, pre);
    int tmp = T - sum[idx] - pre;
    if (k && k >= tmp) {
        ret = max(ret, solve(idx + 1, k - tmp, pre + tmp) + 1);
    }
    return ret;
}
 
void init() {
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i < MAX; i++) {
        sum[i] += sum[i - 1];
    }
}
 
void func() {
    init();
    cout << solve(1, K, 0) << '\n';
}
 
void input() {
    int l, r;
    cin >> N >> M >> K >> T;
    while (M--) {
        cin >> l >> r;
        sum[l]++;
        sum[r]--;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}