문제
중복순열 구하기
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열
하는 방법을 모두 출력합니다.
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.
▣ 입력예제 1
3 2
▣ 출력예제 1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
9
import sys
input=sys.stdin.readline
def DFS(L):
global cnt
if L==m: #하나의 중복 순열이 완성되는 지점
for j in range(m):
print(res[j], 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)
-중복 순열 결과 처리 방법
def DFS(L):
if L==m:
~~
else:
for i in range(1, n+1):
res[L]=i
DFS(L+1)
3 2을 입력하는 경우-->
res[0]=1로 두고 DFS(1)로 넘어간다. 1은 m이 아니므로 else문으로 넘어간다. 다시 else문에서 res[1]=1이다.
DFS(2)로 넘어가지만 m==2이므로 if문으로 넘어가서 결과를 출력한다.
즉 m(중복 순열의 크기) 크기의 리스트를 만들고 그 리스트 각각의 위치에 1부터 n(주어진 숫자)까지의 수로
모든 경우의 수를 작성하는 것이다
순열 구하기 (0) | 2021.08.25 |
---|---|
6.7 동전 교환-Cut Edge Tech (0) | 2021.08.13 |
6.5 바둑이 승차(DFS) (0) | 2021.08.10 |
전역 변수와 지역 변수 (0) | 2021.08.10 |
6.4 합이 같은 부분 집합 (DFS) (0) | 2021.08.09 |
댓글 영역