문제 링크
문제
티어: 골드 1
알고리즘: dp
입력
첫째 줄에 파티가 진행되는 시간 N (1 ≤ N ≤ 300), 파티에 초대한 사람 수 M (1 ≤ M ≤ 300), 영선이의 친구 수 K (1 ≤ K ≤ 300), 욱제가 기대하는 최소의 파티 인원 T (1 ≤ T ≤ M)가 주어진다.
둘째 줄부터 M개의 줄에 걸쳐 각 줄마다 ai, bi가 주어진다. i번째 사람은 시각 ai에 파티에 참여하고, 시각 bi에 파티를 떠난다. (1 ≤ ai ≤ N, ai < bi ≤ N + 1)
파티가 시작되는 시각은 1을 기준으로 한다.
출력
영선이의 친구들을 파티에 투입시켰을 때 욱제가 파티에 머무를 수 있는 최대 시간을 출력한다.
풀이
영선이의 친구들을 파티에 투입시켰을 때 욱제가 파티에 머무를 수 있는 최대 시간을 출력해야 한다.
이 문제는 점화식 유도는 다른 골드 1보다 쉬웠지만, 문제 해석이나 구현 난이도가 조금 더 있는 편이다.
특정 시점에서 생각해보면 간단히 점화식을 유도할 수 있다.
예제 입력 1을 보면
11 3 2 2
3 12
5 10
7 8
여기서 특정 시점 4를 보자,
특정 시점 4에서는 욱제가 아는 사람들이 0명이다.
이때 선택할 수 있는 경우는 두 가지다.
- 영선이의 친구를 투입시키지 않는다.
- 영선이의 친구를 투입시킨다.
두 가지 경우를 적용하게 되면 결국 필요한 상태는
- 현재 투입시킬 수 있는 영선이의 친구가 몇 명인지,
- 현재 투입되어서 유지되고 있는 영선이의 친구가 몇 명인지
이 두 가지 상태가 추가로 필요하다.
그래서 dp[A][B][C]를 정의하면
- A는 현재 시점
- B는 투입시킬 수 있는 영선이의 친구 수
- C는 투입되어서 유지되고 있는 영선이의 친구 수
로 정의할 수 있다.
만약 위 세 가지 상태가 같다면 당연히 지속 시간이 더 큰 값으로 업데이트해 주는 것이 최적 해다.
그리고 투입을 시킨다고 결정했을 때는 파티 인원이 T명이 되게끔 투입시켜줘야 한다.
그 이하든 그 이상을 투입한다면 낭비되는 인원이 발생하기 때문이다.
자세한 구현 사항은 소스 코드를 확인하기 바란다.
이 풀이의 시간 복잡도는 O(N K K)다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, K, T;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
int[] timeLine = new int[N + 2];
for(int i=0; i<M; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st2.nextToken());
int b = Integer.parseInt(st2.nextToken());
for(int j=a; j<b; j++) {
timeLine[j] += 1;
}
}
int[][][] dp = new int[N + 2][K + 1][K + 1];
for(int i=1; i<=N+1; i++) {
for(int j=0; j<=K; j++) {
for(int l=0; l<=K; l++) {
dp[i][j][l] = -1;
}
}
}
dp[1][K][0] = 0;
for(int i=1; i<=N; i++) {
for(int j=0; j<=K; j++) {
for(int l=0; l<=K; l++) {
if(dp[i][j][l] >= 0) {
if(timeLine[i] >= T) {
//T명 이상이면 투입된 영선 친구는 다 나감
dp[i + 1][j][0] = Math.max(dp[i + 1][j][0] , dp[i][j][l] + 1);
} else {
//T명 미만이라면 투입된 영선 친구는 유지됨
if(timeLine[i] + l >= T) {
//현재 욱제 친구들 + 투입된 영선 친구의 합이 T명 이상이라면
dp[i + 1][j][l] = Math.max(dp[i + 1][j][l], dp[i][j][l] + 1);
} else {
//그렇지 않다면 두 가지 유형으로 나눠짐
//type1 영선 친구를 투입하지 않는다.
dp[i + 1][j][l] = Math.max(dp[i + 1][j][l], dp[i][j][l]);
//type2 영선 친구를 투입한다.
//먼저 필요한 인원을 찾음
int need = T - (timeLine[i] + l);
if(need <= j) {
//투입시킬 수 있는 여건이 된다면 투입
dp[i + 1][j - need][l + need] = Math.max(dp[i + 1][j - need][l + need], dp[i][j][l] + 1);
}
}
}
}
}
}
}
int answer = -1;
for(int i=0; i<=K; i++) {
for(int j=0; j<=K; j++) {
answer = Math.max(dp[N + 1][i][j], answer);
}
}
System.out.println(answer);
}
}