문제 링크
문제
티어: 골드 2
알고리즘: dp
1부터 T까지의 범위에 있는 수들이 총 A개 있다. 이들 중 K개를 골라서 집합을 만들 때, 가능한 집합의 개수를 세려 한다. 단, K의 범위는 1 ≤ S ≤ K ≤ B ≤ A로 한다. 즉, 두 정수 S, B를 입력받아서 K = S일 경우, …, K = B일 경우의 집합의 개수를 모두 더하려고 한다.
예를 들어 T=3, 수들이 1, 1, 2, 2, 3인 경우를 생각해 보면, 각기 다음의 경우가 있다.
- K = 1: {1}, {2}, {3}
- K = 2: {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}
- K = 3: {1, 1, 2} {1, 1, 3} {1, 2, 2} {1, 2, 3} {2, 2, 3}
- K = 4: {1, 2, 2, 3} {1, 1, 2, 2} {1, 1, 2, 3}
- K = 5: {1, 1, 2, 2, 3}
따라서 S = 2, B = 3일 경우의 답은 10이 된다.
우리가 일반적으로 이야기하는 집합은 같은 원소를 허용하지 않는다. 이 문제에서의 집합은 같은 원소가 없다는 사실 보다는, 집합의 각 원소들의 순서를 바꾸어도 같은 집합이라는 사실에 주목하여 풀도록 한다. 즉, {1, 1, 2}는 하나의 집합이고, {1, 2, 1}은 이와 같은 집합이다.
입력
첫째 줄에 네 정수 T, A, S, B가 주어진다. 다음 줄에는 A개의 수가 차례로 주어진다.
출력
첫째 줄에 답을 1,000,000으로 나눈 나머지를 출력한다.
풀이
1 ≤ S ≤ K ≤ B ≤ A에서 K가 S일 경우부터 K가 B일 경우까지의 모든 집합의 개수를 구해야 한다.
다음 예시 입력을 보자
3 5 2 3
1 2 2 1 3
T가 1일 때부터 바텀업으로 과정을 설명하면,
- T가 1일 때
- K가 1인 경우 {1}
- K가 2인 경우 {1, 1}
- T가 2일 때
- K가 1인 경우 T가 1일 때 K가 1인 {1}이 들어오는 경우와 {2}가 존재한다.
- K가 2인 경우 전에 구한 값 K가 1일 때의 {1}, {2} 경우 {2, 2}일 때 경우가 존재한다.
- K가 3일 때 ... K가 2일 때의 {1, 1}, {1, 2}, {2, 2} + {2}를 해줘야 하는데 문제점은 2가 최대 2개이기 때문에 K가 2일 때에 2가 두 개 들어가는 경우를 빼줘야 한다.
전에 값에서 특정 원소가 몇 개 들어왔는지 체크하는 건 TLE가 발생하기 때문에 이 문제를 해결해 줘야 한다.
문제점은 2가 초과된 경우와 2가 초과되지 않은 경우를 구분하기 어렵다는 건데
그러면 "2의 개수를 알면 되지 않을까?" 라는 생각을 할 수 있다.
그래서 2의 개수를 고정하는 방법으로 진행해봤다.
예를 들면
T가 2면서, K가 3인 경우
2가 0개 일 때
2가 1개 일 때
2가 2개 일 때
...이렇게 반복하는 것이다.
이렇게 하면 2가 초과되는 경우를 포함하지 않을 수 있으면서, 시간 초과없이 풀 수 있다.
이를 토대로 dp[A][B]를 정의하면
- A는 T의 범위
- B는 1~K
가 된다.
그래서 dp[2][3]이면, 범위가 1 ~ 2이고, 원소가 3개인 집합의 개수다.
dp를 채울 때는 앞에서 말했던 것처럼, 현재 범위에 새로 추가된 수를 0개부터 max까지 고정시켜서 구하면 된다.
이 풀이의 시간 복잡도는 O(T * K)다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static final int MOD = 1000000;
static int T, A, S, B;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
A = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
int[] arr = new int[T + 1];
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i=0; i<A; i++) {
int n = Integer.parseInt(st2.nextToken());
arr[n] += 1;
}
int[][] dp = new int[T + 1][B + 1];
for(int i=1; i<=T; i++) {
for(int j=1; j<=B; j++) {
dp[i][j] = dp[i - 1][j]; //현재 j가 추가되지 않은 경우
for(int k=1; k<=arr[i]; k++) {
if(j < k) {
break;
} else if(j == k) {
dp[i][j] += 1;
} else {
dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
}
}
}
}
int answer = 0;
for(int i=S; i<=B; i++) {
answer = (answer + dp[T][i]) % MOD;
}
System.out.println(answer);
}
}