합이 같은 집합
면접 대비시간 제한3초메모리 제한128 MB
1부터 n까지 수 중에서 원소 k개를 골라 합이 s가 되는 집합 개수를 데이터셋마다 셉니다.
문제
이하의 양의 정수로 이루어진 집합을 생각한다. 집합이므로 원소는 모두 서로 다르고, 원소의 순서는 구분하지 않는다. 즉 {3, 5, 9}와 {5, 9, 3}은 같은 집합이다.
원소의 개수를 , 원소의 합을 로 정해 놓으면 두 조건을 모두 만족하는 집합은 얼마 되지 않는다. , , 이면 {6, 8, 9} 하나뿐이다. 물론 조건을 만족하는 집합이 둘 이상일 때도 있다. , , 이면 {5, 8, 9}와 {6, 7, 9} 두 개다.
주어진 조건을 만족하는 집합의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 데이터 세트로 이루어진다. 데이터 세트의 개수는 100을 넘지 않는다.
각 데이터 세트는 한 줄에 정수 , , 가 공백으로 구분되어 주어진다. , , 이다.
0이 세 개 있는 줄이 입력의 끝을 나타낸다.
출력
데이터 세트마다 조건을 만족하는 집합의 개수를 한 줄에 출력한다. 다른 문자는 출력하지 않는다.
집합의 개수는 을 넘지 않는다.