중복순열 구하기
생성일: 2022년 2월 3일 오후 10:51
구현 코드 ⭐
# 중복순열 구하기
import sys
#sys.stdin = open("input.txt", "rt")
def DFS(index):
global cnt
if index == m:
for x in res:
print(x, end=' ')
print()
cnt += 1
return
else:
for i in range(1,n+1):
res[index] = i
DFS(index+1)
if __name__ == "__main__":
n, m = map(int, input().split())
res = [0] * m
cnt = 0
DFS(0)
print(cnt)
- m 크기의 리스트(res)를 선언한다. (예를들어 m이 2라면 2칸의 리스트가 생성되고 각 칸에는 중복순열이 될 숫자가 한개씩 들어간다)
- 재귀 함수를 돌게 되는데 DFS 함수의 매개변수인 index는 앞서 만든 크기 m의 리스트의 인덱스에 해당한다.
- 각 인덱스의 자리에 들어갈 숫자는 n까지의 수 모두 가능하기 때문에 for문을 사용하여 1부터 n까지의 수를 res에 한칸 씩 넣으면서 재귀로 호출한다. (첫번째 칸에 n까지의 수를 넣은 n개의 res 경우의 수가 생기고 DFS를 호출하여 다음칸에 또 n개의 수를 넣은 n개의 경우의 수 생성)
- 입력 파라미터(index)가 m이 되면 base case가 되어서 재귀를 멈추고 res 리스트를 출력하고 cnt를 1 증가시킨다.
⇒ 요약
중복 순열의 경우의 수를 담은 res 리스트 관점에서 index를 1씩 증가시키면서 n개의 수를 각 칸에 담은 경우의 수를 만들고 다음 인덱스로 넘어간다.
Author And Source
이 문제에 관하여(중복순열 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/중복순열-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)