문제 / 중복순열 구하기 ( itertools product ) / Python 파이썬

 

문제 제목: 중복 순열 구하기

1부터 N까지 번호가 적힌 구슬이 있습니다.

 

이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.

 

▣ 입력설명

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

▣ 출력설명

첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다. ▣ 입력예제

3 2

▣ 출력예제 

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

9

---

나의 풀이

from itertools import product
def solution(n,m):

    arr = [ i for i in range(1,n+1)]
    cnt = 0

    for i in product(arr, repeat = m):
        cnt += 1
        answer = ""
        for j in i:
            answer += str(j)
            answer += " "
        print(answer[:-1])



    return cnt

if __name__ == "__main__":
    n, m = map(int,input().split())

    print(solution(n,m))

모범답안 - DFS 풀이

import sys
sys.stdin=open("input.txt", "r")
def DFS(L):
    global cnt
    if L==m:
        for i in range(m):
            print(res[i], end=' ')
        print()
        cnt+=1
    else:
        for i in range(1, n+1):
            res[L]=i
            DFS(L+1)

if __name__=="__main__":
    n, m=map(int, input().split())
    res=[0]*m
    cnt=0
    DFS(0)
    print(cnt)

 

그림을 그렸긴 했는데 너무 대충 그린거 같다

 

아모튼

res = [0] * m 

이런 식으로 m의 크기만큼 중복 순열을 저장하며 DFS를 돌 수 있게 만듦

 

스택에 계속 쌓여서 res 를 출력하게되면 D(2) 는 pop 된다

 

이런식으로 1,2,3 가지를 다 돌면 D(1) 도 pop 된다.

그러면 D(0) 에서 2로 가고 똑같은 것 반복

이렇게해서 스택에 메모이제이션 하고 pop을 반복하며 값을 출력하게된다...

---

※ 알아야 할 것

- DFS는 stack 메모이제이션임 명심명심!