.PNG)
47. 중복순열 구하기
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
<내 풀이>
- 내가 구현하고 싶었던 건 n(예제로 따지면 0123 존재하는 리스트)길이 만큼의 리스트에 중복되어서 나오는 경우의 수라도 다 부분집합 구하고 나온 숫자는 리스트에 1로 대체하다가 마지막에 if x==n: 걸리면 리스트 합이 2인 것을 출력하는데 그 리스트 안에서도 값이 0이 아닌 애들만을 출력하고 싶었다 근데 그 중복이 되는 부분집합 경우의 수를 구하지 못하겠다
def DFS(x):
if x==n+1:
if sum(ch)==2:
for i in sum:
if i!=0:
print(i, end=' ')
else :
for i in range(m) :
######여기를 대체 구현하지 못하겠다ㅠㅠ
DFS(x+1)
if __name__=='__main__' :
n,m=map(int, input().split())
ch=[0]*(n+1)
DFS(1)
- 풀이를 보고 구현해보려고 하는데 왜인지 모르게 자꾸 막힌다
def DFS(x):
global cnt
if x==m:
for i in res:
if i!=0:
print(res.index(i)+1, end=' ')
cnt+=1
print()
return
else :
for i in range(n):
res[i]=1
DFS(x+1)
if __name__=='__main__' :
n,m=map(int, input().split())
res=[0]*n
cnt=0
DFS(0)
print(cnt)=>else 부분에서 res[i]가 같은 DFS(L)에서 같은 L레벨일 때 자꾸 누적되는 것 같다ㅠ
그때는 따로따로 res[1,0,0] / res[0,1,0] / res[0,0,1] 이런식으로 들어가야 하는데 말이다. 이걸 어떻게 해야지 res가 적당히 초기화 될 수 있을지 모르겠다
<풀이>
def DFS(x):
global cnt
if x==m:
for i in range(m): #이 부분또한...
print(res[i], end=' ')
cnt+=1
print()
return
else :
for i in range(1,n+1): #1, 2, 3
res[x]=i #이 부분을 잘못 했었다..
DFS(x+1)
if __name__=='__main__' :
n,m=map(int, input().split())
res=[0]*n
cnt=0
DFS(0)
print(cnt)
<반성점>
- 다 비슷한 전개로 진행되는데 발전시켜나가질 못한다
<배운 점>
- D(0)-D(1)D(1)D(1)-D(2)D(2)D(2) 이런 식으로 진행
- res라는 [0]식을 활용
<2회독 내 풀이>
def DFS(x) :
if x==m:
for i in ch:
print(i, end=' ')
print()
return
else :
for i in range(1,n+1) :
ch[x]=i
DFS(x+1)
if __name__=='__main__' :
n, m=map(int, input().split())
ch=[0]*m
DFS(0)
