중복순열 구하기

생성일: 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개의 수를 각 칸에 담은 경우의 수를 만들고 다음 인덱스로 넘어간다.