어떤 프로그래밍 대회에서는 경기를 끝마치고 나면 뒤풀이로 빙고 게임을 하는 이상한 관습이 있다고 합니다. 하지만 이 빙고 게임에서 사용되는 "빙고 표"는 보통 빙고 게임과 다르게 밑에 있는 조건에 따라 빈 칸을 채워야 합니다.
빙고 표는 N 행 N열의 숫자 칸으로 나눠져있으며 각 숫자 칸에는 정수 1개가 적혀 있습니다. 적힌 정수는 모두 달라야 합니다.
숫자 칸에 적혀 있는 정수는 1 이상 M 이하입니다.
빙고 표에 적혀 있는 N × N개의 정수의 합은 S입니다.
모든 줄에서 위에서 아래로 보면 숫자들이 오름차순으로 정렬되어 있어야 합니다.
숫자 칸에 적혀있는 정수는 자신의 왼쪽 방향 줄에 있는 모든 정수보다 큰 값이어야 합니다.
아래 그림은 N = 5, M = 50, S = 685일 때 빙고 표 배치로 나올 수 있는 예입니다.
뒤풀이에 참석하고 싶어하는 사람이 많기 때문에 될 수 있는 한 많은 빙고 표를 만들려고 합니다. 하지만 모든 사람들은 자신만의 빙고 표를 갖고 싶어합니다. 그러므로 같은 빙고 표를 2개 이상 만들어선 안 됩니다. 만들 수 있는 빙고 표 개수의 최댓값을 100,000으로 나눈 값을 출력하는 프로그램을 작성하세요.
입력은 1줄입니다. 그 줄에는 각각 빙고 표의 크기 N(1 ≤ N ≤ 7)과 숫자 칸에 적혀 있는 정수들의 최댓값 M(1 ≤ M ≤ 2000), 빙고 표에 적혀 있는 정수의 합계인 S(1 ≤ S ≤ 3000)을 나타내는 3개의 정수가 공백으로 구분되어 주어집니다.
주어지는 모든 입력 데이터에 대해서, 조건을 만족하는 빙고 표를 적어도 1개 이상 만드는 것이 가능합니다.
출력
만들 수 있는 빙고 표 개수의 최댓값을 100,000으로 나눈 값을 출력하세요.
입력 예시
3 9 45
출력 예시
1
풀이
빙고판의 규칙을(그리고 예시로 주어진 그림도 포함하여) 잘 살펴보면, [1, M]에 속하는 수를 중복을 포함하지 않고 총 N^2개 뽑아, 그 합이 S가 되게 하는 경우의 수를 구하는 문제로 치환할 수 있다. 즉 배낭 문제(DP)와 비슷한 문제이다.
1부터 M까지의 수(i)를 하나씩 사용할 것이다.
DP[j][k]는 총 j개의 숫자를 골랐을 때, 그 합이 k인 경우의 수이다.
즉 다음 식이 성립한다.
DP[j][k] = DP[j][k] + DP[j-1][k-i]
j-1번째 수까지 뽑았을때의 합이 k-i라면, j번째를 뽑았을 때 i를 사용하여 그 합이 k가 될 것이다.
주의;할 점은, j를 순환할 때 내림차순으로 순환해야 한다. 오름차순으로 순환하게 되면 i를 중복해서 사용하게 된다.
(j, k) -> (j+1, k+i) -> (j+2, k+2*i)....
풀이 코드
MOD = 100000
N, M, S= map(int, input().split())
dp = [[0]*(S+1) for _ in range(N**2+1)]
dp[0][0] = 1
for i in range(1, M+1) :
for j in range(N**2, -1, -1) :
for k in range(i, S+1) :
dp[j][k] = (dp[j][k] + dp[j-1][k-i]) % MOD
print(dp[-1][-1] % MOD)
