15657

문제풀이

N개의 자연수 중에서 M개를 골라서 고른 수열을 비내림차순으로 출력하는 중복 조합 문제입니다.

수식은 다음과 같습니다. (문제와는 무관하나 디버깅에서 활용)

$$ _n\hat{C}_r = \frac{(n+r-1)!}{(n-1)!r!} $$

순열 vs 조합 구분하기

15656과 비교하면 "고른 수열은 비내림차순이어야 한다" 라는 조건만 차이가 있습니다. 이것은 한 가지 수열에 대해서 비내림차순으로 정렬한 수열 1번만 인정되는것으로 순서가 중요하지 않은 조합 문제입니다.

입력

• n, m : n개 중에 m개를 고릅니다.
• arr : 자연수가 n개 주어집니다.

로직

• 자연수를 항상 m개만 고르면 되기 때문에 m개를 담을 임시배열을 사용해서 m개가 채워질 때마다 result배열에 담아서 누적한다.

맞왜틀

리팩토링

• 누적해서 저장하면 push, pop 보다 연산이 조금 더 빠르다.