문제
조합 구하기
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그
램을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.
▣ 입력예제 1
4 2
▣ 출력예제 1
1 2
1 3
1 4
2 3
2 4
3 4
6
풀이
def DFS(L, s):
global cnt
if L==m:
for j in res:
print(j, end=' ')
cnt+=1
print()
else:
for i in range(s,n+1):
if ch[i]==0:
ch[i]=1
res[L]=i
DFS(L+1,i+1) #s+1이 아니라 i+1임
ch[i]=0
if __name__=="__main__":
cnt=0
n,m=map(int, input().split())
ch=[0]*(n+1)
res=[0]*m
DFS(0, 1)
print(cnt)
-DFS(L, s)
L: Level 층위
s: start 가지의 머리 부분을 의미한다.
-
else:
for i in range(s,n+1):
if ch[i]==0:
ch[i]=1
res[L]=i
DFS(L+1,i+1) #s+1이 아니라 i+1임
ch[i]=0
DFS(L+1, s+1)로 코드를 잘못 작성했었음-->틀린 코드
s부터 n까지를 i에 대입해서 돌리고 있으므로 i를 대입해야 한다. s는 고정값이다. 범위에 맞는 모든 값을
넣어야 하기 때문에 i+1로 대입해야 한다.
인접 행렬 python (0) | 2021.08.26 |
---|---|
수들의 조합(DFS) (0) | 2021.08.25 |
수열 추측하기 (0) | 2021.08.25 |
순열 구하기 (0) | 2021.08.25 |
6.7 동전 교환-Cut Edge Tech (0) | 2021.08.13 |
댓글 영역