🔥

문제

어떤 수 n을 주어진 수들의 합으로 표현할 수 있는 방법의 수를 세어보자.


예를 들면 3을 1과 2로 분할하고자 한다면 아래와 같이 3가지 방법이 있다.


3 = 1 + 2 = 2 + 1 = 1 + 1 + 1

입력

첫째 줄에 주어질 수의 개수 x와 표현할 수 n이 주어진다. (1 ≤ x ≤ 100), (1 ≤ n ≤ 10^6)


둘째 줄에 x개의 수들(xi)이 주어진다. (1 ≤ xi≤ 10^6)

출력

표현할 수 n을 x개의 주어진 수들의 합으로 표현할 수 있는 방법의 수를 10^9 - 7로 나눈 나머지를 출력한다.

예제 1 입력

3 9
2 3 5

예제 1 출력

8

Source

x, n = map(int, input().split())
arr = list(map(int, input().split()))

# dp(N): N을 주어진 수들의 합으로 표현하는 경우의 수=
# dp(x) = dp(x – arr[0]) + dp(x-arr[1]) + ...
dp = [0 for _ in range(n + 2)]
dp[0] = 1

for i in range(1, n + 1):
	for j in range(x):
		if(i - arr[j] >= 0):
			dp[i] = (dp[i] + dp[i - arr[j]]) % 1000000007

print(dp[n])

참고