수열
면접 대비시간 제한2초메모리 제한512 MB
1부터 m까지의 수로 길이 n인 비내림차순 수열을 만들 때 각 수가 k번 이하 등장하는 경우의 수를 구합니다. 마지막 수와 등장 횟수를 상태로 잡습니다.
문제
1부터 m까지의 정수로 이루어진 길이 n의 비감소 수열 중에서 각 원소가 최대 k번까지만 등장하는 수열의 개수를 세는 프로그램을 작성하시오.
입력
표준 입력으로 정수 n, m, k가 공백으로 구분되어 주어진다.
출력
표준 출력으로 조건을 만족하는 수열의 개수를 출력한다.
제한
- 0 < n < 31
- 0 < m < 31
- 0 < k < 31
힌트
수열은 다음과 같다: (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,3), (1,2,4), (1,3,3), (1,3,4), (1,4,4), (2,2,3), (2,2,4), (2,3,3), (2,3,4), (2,4,4), (3,3,4), (3,4,4).