moner_ari   1년 전

[문제]

n 이하 자연수로 구성된 집합을 고려해 봅시다. 이때 집합의 모든 원소는 서로 다른 자연수입니다. 또한, 집합에서 원소의 순서는 고려하지 않습니다. 즉, {3, 5, 9}와 {5, 9, 3}은 동일한 집합입니다.

집합의 원소의 개수를 k, 이들 원소의 합을 s라고 합시다. 이때 k, s의 값이 정해진다면, 이들 조건을 만족하는 집합은 제한적입니다. 예를 들어 n = 9, k = 3, s = 23이라면, 조건을 충족하는 집합은 {6, 8, 9} 하나뿐입니다. 하지만 일반적으로는 조건을 충족시키는 집합이 여러 개 존재할 수 있습니다. 예를 들어 n = 9, k = 3, s = 22라면, {5, 8, 9}와 {6, 7, 9}는 모두 조건을 만족시킵니다.

n, k, s가 주어졌을 때, 조건을 만족하는 집합의 개수를 구하는 프로그램을 작성하세요.

--------

[입력]

입력은 여러 개의 테스트 케이스로 구성되어 있습니다. 테스트 케이스의 개수는 최대 100개입니다.

각 테스트 케이스는 한 줄에 하나씩 주어지며, 자연수의 개수 n, 집합의 원소 개수 k, 집합의 원소들의 합 s가 띄어쓰기로 구분되어 한 줄에 주어집니다. 이때 1 ≤ n ≤ 20, 1 ≤ k ≤ 10, 1 ≤ s ≤ 155가 성립합니다.

입력의 마지막 줄에는 "0 0 0"이 주어집니다.

--------

[출력]

각 테스트 케이스마다 조건을 충족하는 집합의 개수를 한 줄에 출력합니다. 모든 입력 데이터에서 '조건을 충족하는 집합의 개수'는 231 - 1 이하임이 보장되어 있습니다.

댓글을 작성하려면 로그인해야 합니다.