[백준] Gold2 - 2092 집합의 개수

집합의 개수

문제 설명

1 이상 T 이하의 수로 이루어진 정수들이 A개 주어진다. 이 때 A개의 정수중 S개 이상 B개 이하의 원소로 구성된 부분 집합을 구성할 수 있는 경우의 수를 구하는 문제이다. 중복은 허용되지 않는다는 점이 중요하다.

접근 방법

우선 주어진 예제를 살펴보자 T = 3 A = 5 S = 2 B = 3

즉 3 이하의 수로 이루어진 길이 5의 배열이 주어지고 이 중 원소의 수가 2개 이상 3개 이하인 부분집합의 개수를 구하는 문제이다.

우선 A의 길이를 모두 고려해서 패턴을 구해보자

K	집합	개수
1	{1},{2},{3}	3
2	{1, 1}, {1, 2}, {2, 2}, {1, 3}, {2, 3}	5
3	{1, 1, 2} {1, 1, 3} {1, 2, 2} {1, 2, 3} {2, 2, 3}	5
4	{1, 2, 2, 3} {1, 1, 2, 2} {1, 1, 2, 3}	3
5	{1, 1, 2, 2, 3}	1

위와 같이 경우의 수가 나누어지고 문제의 주어진 예제 S=2 B=3 일때는 각 각 5개의 집합이 존재하므로 답은 10이 된다.

입력의 크기 상 Greedy 또는 Brutal Force 로는 해결이 불가능 하기 때문에 동적계획법을 이용해본다.
위의 표를 이용 가능한 숫자의 최대값과 집합의 길이를 통해 약간 변형을 시켜보자

숫자 제한	길이	집합	개수
1	1	{1}	1
1	2	{1, 1}	1
2	1	{1}, {2}	2
2	2	{1, 1}, {1, 2}, {2, 2}	3
2	3	{1,1,2}, {1,2,2}	2
3	1	{1}, {2}, {3}	3
3	2	{1, 1}, {1, 2}, {2, 2}, {1, 3}, {2, 3}	5
3	3	{1, 1, 2}, {1, 2, 2}, {1, 2, 3}, {1, 1, 3}, {2, 2, 3}	5

여기서 규칙을 찾을 수 있다. 위 표에서 집합 열을 F(X,Y)로 표현하자

X 이하의 수로 이루어진 길이 1의 집합의 수는 해당 숫자로 이루어진 진합 하나를 무조건 포함한다.(단, 입력 배열에 숫자가 존재할 시)
X 이하의 수로 이루어진 길이 Y의 집합은 X-1 이하의 수로 이루어진 길이 Y의 집합을 포함한다.
X 이하의 수로 이루어진 길이 Y의 집합은 X의 개수를 K라고 했을 때, 폐구간 [1, K]에 속하는 값 J 대하여 Y-J > 0 을 만족하는 F(X-1, Y-J)에 X를 J개 추가한 패턴을 추가로 가진다.

1번 조건에 해당하는 부분을 파랑색으로 표기해두었고,
2번 조건에 해당하는 부분을 F(2, 1)과 F(1, 1) 의 예로 표기해두었다. 3번 조건에 해당하는 부분은 아래 테이블에서 다시 살펴보자

숫자 제한	길이	집합	개수
1	1	{1}	1
1	2	{1, 1}	1
2	1	{1}, {2}	2
2	2	{1, 1}, {1, 2}, {2, 2}	3
2	3	{1,1,2}, {1,2,2}	2
3	1	{1}, {2}, {3}	3
3	2	{1, 1}, {1, 2}, {2, 2}, {1, 3}, {2, 3}	5
3	3	{1, 1, 2}, {1, 2, 2}, {1, 2, 3}, {1, 1, 3}, {2, 2, 3}	5

예제에서는 3이 1개까지 사용이 가능하며, F(3, 2)는 F(2, 2)(빨강색) 를 우선 포함한다. 나머지 {1, 3}, {2, 3}은 F(2, 1)에 3을 하나 추가하면 만들 수 있는 경우이다.

F(3, 3)을 살펴보자. 마찬가지로 F(2, 3)(터키옥색)을 포함한다. 여기에 초록색으로 표기된 부분이 추가되는데, 이 수는 F(2, 2)에 3을 하나 추가한 경우의 수에 해당한다. 만약 여기서 3이 두개 존재했다면, F(2, 1) 에다가 3을 두개 붙인 패턴이 추가될 것이다.

이제 여기서 점화식을 도출할 수 있다.

dp[i][j] = dp[i][j] + dp[i-1][j]
dp[i][j] = dp[i][j] + dp[i-1][j-k] for k in range(1, count[i]), count[i] = 주어진 입력에서 i의 갯수이며, j-k > 0 이 만족해야한다.

소스 코드

import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;
import java.io.*;

public class Main {

    static void testRun(int no) throws IOException {
        Path base = Paths.get("");
        System.out.println("base path : " + base.toAbsolutePath());
        String testFileDirName = base.toAbsolutePath() + "/src/main/resources/examples/" + String.valueOf(no);
        File dir = new File(testFileDirName);
        File[] files = dir.listFiles();

        if(files == null) {
            return;
        }

        for(int i = 0 ; i<files.length ; i++){
            String fileName = files[i].getName();
            String fullPath = testFileDirName + "/" + fileName;
            System.out.println("Test file name : " + fullPath);
            BufferedReader reader = new BufferedReader(new FileReader(fullPath));
            reader.mark(262144);
            reader.lines()
                    .forEach(System.out::println);
            reader.reset();

            System.out.println("answer ");
            new Solution(reader).run();
            reader.close();
        }
    }

    static void run() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        new Solution(reader).run();
        reader.close();
    }

    public static void main(String[] args) throws IOException {
        // testRun(2092);
        run();
    }
}

class Solution {

    int T,A,S,B;
    
    // int[] arr;
    
    int[] numCnt;
    
    public Solution(BufferedReader reader) throws IOException {
        String[] line = reader.readLine().split(" ");
        T=Integer.parseInt(line[0]);
        A=Integer.parseInt(line[1]);
        S=Integer.parseInt(line[2]);
        B=Integer.parseInt(line[3]);

        numCnt = new int[T+1]; // 해당 숫자의 사용 가능한 개수

        line = reader.readLine().split(" ");
        for(int i = 1 ; i <= A ; i++) {
            // arr[i] = Integer.parseInt(line[i-1]); // 필요없어짐
            int num = Integer.parseInt(line[i-1]);
            numCnt[num]++;
        }
    }



    public void run() {
        int answer = 0;
        int mod = 1000000;
        int[][] memo = new int[T+1][A+1];

        for(int i = 1 ; i <= T ; i++) {
            for(int j = 0 ; j <= numCnt[i] ; j++) {
                memo[i][j]++; // 조건 1
            }

            for(int j = 1 ; j <= A ; j++) {
                memo[i][j] = (memo[i][j] + memo[i-1][j])%mod; // 조건 2
                for(int k = 1 ; k <= numCnt[i] ; k++) {
                    if(j-k > 0) {
                        memo[i][j] = (memo[i][j] + memo[i-1][j-k]) % mod;//조건 3
                    }
                }                
            }
        }

        for(int i = S ; i <= B ; i++) {
            answer= (answer + memo[T][i])%mod;
        }

        System.out.println(answer);
    }
}

후기

동적 계획법 문제는 Gold 3 이상부터는 점화식을 도출하기가 쉽지 않다. 기업 코딩 테스트에서 굉장히 많이 등장하는게 동적 계획법이지만, 굉장히 의문점이 많이 드는 부분이기도 하다. 프로그래밍의 핵심은 논리적 사고를 설계를하고 설계 내용을 프로그래밍 언어를 이용하여 기술하는 것이라고 생각한다. 어느 순간부터 수학 문제를 풀고나면 몇줄 안되는 코드로 답이 도출되는 하지만 그 수학문제가 굉장히 어려운 형태가 많이 보이고 있다. 이러면 그냥 수학 실력을 보는게 아닌가 싶기도 하고...