만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

합이 같은 집합

면접 대비

시간 제한3초메모리 제한128 MB

요약
1부터 n까지 수 중에서 원소 k개를 골라 합이 s가 되는 집합 개수를 데이터셋마다 셉니다.
난이도

쉬움10점 중 3점

유형
동적 계획법, 조합론
정답자
아직 제출이 없습니다

문제

nn 이하의 양의 정수로 이루어진 집합을 생각한다. 집합이므로 원소는 모두 서로 다르고, 원소의 순서는 구분하지 않는다. 즉 {3, 5, 9}와 {5, 9, 3}은 같은 집합이다.

원소의 개수를 kk, 원소의 합을 ss로 정해 놓으면 두 조건을 모두 만족하는 집합은 얼마 되지 않는다. n=9n = 9, k=3k = 3, s=23s = 23이면 {6, 8, 9} 하나뿐이다. 물론 조건을 만족하는 집합이 둘 이상일 때도 있다. n=9n = 9, k=3k = 3, s=22s = 22이면 {5, 8, 9}와 {6, 7, 9} 두 개다.

주어진 조건을 만족하는 집합의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 데이터 세트로 이루어진다. 데이터 세트의 개수는 100을 넘지 않는다.

각 데이터 세트는 한 줄에 정수 nn, kk, ss가 공백으로 구분되어 주어진다. 1≤n≤201 \le n \le 20, 1≤k≤101 \le k \le 10, 1≤s≤1551 \le s \le 155이다.

0이 세 개 있는 줄이 입력의 끝을 나타낸다.

출력

데이터 세트마다 조건을 만족하는 집합의 개수를 한 줄에 출력한다. 다른 문자는 출력하지 않는다.

집합의 개수는 231−12^{31} - 1을 넘지 않는다.

예제1

  1. 예제 1

    입력
    9 3 23
    9 3 22
    10 3 28
    16 10 107
    20 8 102
    20 10 105
    20 10 155
    3 4 3
    4 2 11
    0 0 0
    
    예상 출력
    1
    2
    0
    20
    1542
    5448
    1
    0
    0