boj 17258 인기가 넘쳐흘러

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

 

어디서 많이 본 문제네요!

월클병에 걸려버린 욱제가 파티 인원이 T명 이상일 때만 파티에 참여한다고 합니다.

친구를 최대 K명까지 투입하여 파티에 참여하는 시간을 최대로 만들어야 하는 문제입니다.

그 친구들은 친구들을 제외한 나머지 인원이 T명 이상이면 파티를 모두 나간다고 합니다.

그래서 적절한 시기에 친구들을 투입해야 최대를 구할 수 있습니다.

 

저는 dp를 활용했고, 파티 참여 인원을 구하기 위해 누적합을 추가했습니다.

imos 기법을 활용하여 시작과 끝 지점에만 카운팅을 해주고, 마지막에 누적합을 구해줍니다.

 

dp[N][K][pre]: N 시간에 친구 K명을 부를 수 있고, 파티에 참여중인 친구가 pre명일 때 파티에 머무르는 최대 시간

dp를 이렇게 구성했지만 2차원 배열로도 푸신분이 계시더라고요..? 전 모르겠습니다

 

문제에서 생각해볼 경우들은

1. 누적합이 이미 T 이상인지

2. 이전부터 참여중인 친구들과 합쳐서 T 이상인지

3. 파티를 유지할 수 있도록 친구들이 추가될 수 있는지

이렇게 3가지가 되겠습니다.

 

누적합이 이미 T 이상이라면 파티가 유지될 수 있으므로 +1을 하고 다음 시간을 확인합니다.

이때 친구들을 제외한 인원들이 T 이상이므로 참여하고 있던 친구들은 모두 빠져나갑니다.

 

이전부터 참여중인 친구들과 합쳐서 T 이상이라면 파티가 유지될 수 있으므로 +1을 하고 다음 시간을 확인합니다.

이때 친구들을 제외하면 T보다 작으므로 참여하고 있던 친구들은 계속 참여합니다.

 

파티를 유지할 수 있도록 친구들이 추가될 수 있다면 부족한 인원을 채워줄지, 아니면 친구들을 추가하지 않고 다음 시간을 확인할 지 선택합니다.

친구들을 추가한다면 +1을 해주고, 둘중 최대를 구합니다.

친구를 추가할 수 없다면 다음 시간을 보는것 밖에 없습니다.

 

 

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 310
using namespace std;
 
int dp[MAX][MAX][MAX];
int sum[MAX];
int N, M, K, T;
 
int solve(int idx, int k, int pre) {
    if (idx == N + 1) return 0;
 
    int& ret = dp[idx][k][pre];
    if (ret != -1) return ret;
 
    if (sum[idx] >= T) {
        return ret = solve(idx + 1, k, 0) + 1;
    }
    if (sum[idx] + pre >= T) {
        return ret = solve(idx + 1, k, pre) + 1;
    }
 
    ret = solve(idx + 1, k, pre);
    int tmp = T - (sum[idx] + pre);
    if (tmp <= k) {
        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;
}