15656

문제풀이

N개의 자연수 중에서 M개를 골라서 나열하는데 중복 선택이 가능하므로 중복 순열문제 입니다.

중복 순열의 경우의 수를 구하는 식은 다음과 같습니다. $$ _n\hat{P}_r = n^r $$

입력

• n, m: $_nC_m$
• arr: 수열

로직

두번째 입력 예제로 4개중에 2개를 고르는 중복조합의 경우의 수는 $_4\hat{P}_2$로 $4^2$이 16개의 경우의 수가 되어야 합니다.

1. m이 1인경우 경우의 수는 항상 n이므로 예외처리 합니다.
2. 중복조합이므로 재귀함수안에서 0부터 반복문을 시작합니다.
3. tmp에 m까지 선택한 값을 저장하고 재귀함수를 호출한 이후에는 pop함수로 제거합니다.

맞왜틀

• 중복 선택이 된다는걸 순서가 상관없다는 말로 잘못보고 조합이라고 생각하고 풀고 있었다.
• 중복 순열과 중복 조합 학습을 추가로 진행했다.

리팩토링

• 처음 작성한 로직이 가장 메모리가 적게들고 속도가 빠릅니다.