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을 해주고, 둘중 최대를 구합니다.
친구를 추가할 수 없다면 다음 시간을 보는것 밖에 없습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#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;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 19623 회의실 배정 4 (0) | 2024.07.29 |
|---|---|
| boj 30461 낚시 (0) | 2024.07.28 |
| boj 1398 동전 문제 (0) | 2024.07.04 |
| boj 1229 육각수 (0) | 2024.06.30 |
| boj 25378 조약돌 (0) | 2024.06.29 |