수열
면접 대비시간 제한2초메모리 제한128 MB
합이 M이고 비내림차순인 길이 N의 양의 정수 수열들 중 사전순으로 K번째 수열을 구하는 문제입니다.
문제
정수 N, M, K가 주어진다. 자연수로 이루어진 길이 N의 수열 A1, A2, ..., AN 중에서 다음 두 조건을 모두 만족하는 수열을 모두 생각하자.
- A1 <= A2 <= ... <= AN
- A1 + A2 + ... + AN = M
이 수열들을 사전순으로 정렬했을 때 K번째 수열을 출력한다. 답이 존재하는 입력만 주어진다.
입력
첫째 줄에 세 정수 N, M, K가 주어진다. (1 <= N <= 10, 1 <= M <= 220, 1 <= K <= 2147483647)
출력
합이 M인 길이 N의 수열 중 사전순으로 K번째인 수열을 한 줄에 출력한다. 인접한 수는 공백 하나로 구분한다.