중복순열 구하기

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

---

상태트리 그리기

상태트리

 

내가 쓴 코드

import sys
sys.stdin = open("input.txt",'rt')

def DFS(length,subset):
    if length == M:
        for x in subset:
            print(x, end=' ')
        print()
    else:
        for i in range(1,N+1):
            subset.append(i)
            DFS(length+1,subset)
            subset.pop()

if __name__=="__main__":
    N, M = map(int, input().split())
    DFS(0,[])
    print(N**M)

 

모범답안

#모범답안
import sys
sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline

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)

 

느낀점

1. 지금까지 상태 트리를 넣고 안넣고 두갈래로 나뉘는 DFS 문제만 풀었어서
for문을 써서 가지 수를 늘리는 생각을 안했었다. 
비슷한 문제를 많이 풀고 분석해서 DFS를 정복해보쟝!

2. 함수의 매개변수로 리스트를 넣는 것 보다 리스트를 하나 만들고
그걸 참조해서 값 변경을 통해 결괏값들을 내는 방법도 써보자
보통 모범답안은 그런식으로 해결을 하네 ..

---

다시 풀어보기

#다시 풀어보기

import sys
sys.stdin = open("input.txt")
input = sys.stdin.readline

def DFS(L):
    global cnt
    if L == M:
        for x in result:
            print(x, end=' ')
        print()
        cnt += 1
    else:
        for i in range(1,N+1):
            result[L] = i
            DFS(L+1)

if __name__ == "__main__":
    N, M = map(int, input().split())
    result = [0]*M
    cnt = 0
    DFS(0)
    print(cnt)