[python] 백준 2092 집합의 개수

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

2092번: 집합의 개수

 

 

문제 해결

• 각 숫자의 개수를 알 수 있도록 numbers[num]을 통해 개수를 저장한다.
• dp[i][j] 를 i까지 숫자중 j개 사용했을 때 가지수를 나타내는 dp함수를 만든다
• 기본적으로 숫자 i가 k개 있을 때 k개이하를 쓸 수 있으므로 dp[i][j] += 1씩 해준다. (j<=k)
• i를 집합안에 안넣는 경우가 있으므로 dp[i][j] += dp[i-1][j]를 해준다.
• i가 k개 있을 때 숫자 i까지 집합안에 넣을 개수가 j개가 있다고 하자 j>=k 일때 dp[i][j] += dp[i-1][j-k]이다.
• 숫자를 1000000으로 나눠주라고 했으므로 dp[i][j]%=1000000을 잊지 말자

 

 

CODE

import sys
input = sys.stdin.readline
MOD = 1000000

def check(a):
    for i in range(a):
        numbers[A[i]] += 1

def cal():
    for i in range(1,t+1):
        for k in range(numbers[i]+1): # i번째 숫자를 k번 사용
            dp[i][k] += 1
        for j in range(1,a+1):
            dp[i][j] += dp[i-1][j] # i번째 사용안하고 i-1까지 총 j개 사용
            for k in range(1,numbers[i]+1):
                if j-k >0:
                    dp[i][j] += dp[i-1][j-k]
                    dp[i][j] %= MOD


if __name__=='__main__':
    t, a, s, b = map(int, input().split())
    A = list(map(int, input().split()))
    total = 0
    dp = [[0 for _ in range(4010)] for _ in range(210)]
    numbers = [0 for _ in range(210)]
    check(a) # 각 숫자의 개수 확인
    cal()
    for i in range(s,b+1): # t까지 s부터 b 개수만큼 사용한 개수 합 구하기
        total += dp[t][i]%MOD
    print(total%MOD)