integer partition5 -최댓값이 제한된 상태에서 원소의 합이 n이 되는 방법의 수 구하기-
1. 문제
9599번: Equal Sum Sets (acmicpc.net)
9599번: Equal Sum Sets
Let us consider sets of positive integers less than or equal to n. Note that all elements of a set are different. Also note that the order of elements doesn’t matter, that is, both {3, 5, 9} and {5, 9, 3} mean the same set. Specifying the number of set e
www.acmicpc.net
2. 풀이
이번엔 집합의 원소 최댓값이 n이면서 k개의 서로 다른 정수를 사용하고 합이 s가 되는 방법의 수를 구하는 문제
dp[s][k][n]을 최댓값이 n이고 k개의 서로 다른 정수를 사용하여 합이 s가 되는 방법의 수
그러면 최댓값이 n = 1,2,...,20까지 모든 경우 각각에 대하여...
k-1개의 서로 다른 정수를 사용해서 합이 s-i가 되는 경우의 수 dp[s-i][k-1][n] 각각에 i만 더해주면 된다
여기서 이전에 서로 다른 소수의 합을 구하는 문제에서 배운 테크닉으로...
k를 역으로 순회해서 동일한 정수를 사용하는 경우를 피하자
https://deepdata.tistory.com/1020
integer partition4 -서로 다른 소수의 합으로 자연수를 만드는 방법의 수(역으로 순회하는 테크닉)-
1. 문제 3908번: 서로 다른 소수의 합 (acmicpc.net) 3908번: 서로 다른 소수의 합 양의 정수는 서로 다른 소수의 합으로 나타낼 수 있다. 두 정수 n과 k가 주어졌을 때, n을 서로 다른 k개의 소수의 합으로
deepdata.tistory.com
from sys import stdin
#dp[s][k][n]을 최댓값이 n이고 k개의 서로 다른 정수를 사용하여 합이 s가 되는 방법의 수
dp = [[[0]*21 for _ in range(11)] for _ in range(156)]
#0개의 서로 다른 정수로 0을 만드는 방법은 아무것도 안하면 되니까 1로 초기화
for i in range(21):
dp[0][0][i] = 1
#최댓값이 n = 1,2,...,20까지 모든 경우 각각에 대하여...
#k-1개의 서로 다른 정수를 사용해서 합이 s-i가 되는 경우의 수 dp[s-i][k-1][n] 각각에 i만 더해주면 된다
for n in range(1,21):
for i in range(1,n+1):
#k를 역으로 순회해서 동일한 정수를 사용하는 경우를 피한다
for k in range(10,0,-1):
for s in range(1,156):
if s >= i:
dp[s][k][n] += dp[s-i][k-1][n]
while 1:
n,k,s = map(int,stdin.readline().split())
if n == 0 and k == 0 and s == 0:
break
else:
print(dp[s][k][n])