10.조합구하기

조합구하기

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

 

문제풀이

import sys
sys.stdin=open("input.txt", "r")
def DFS(L, s):
    global cnt
    if L==m: #2개를 뽑은 경우 m=2 
        for j in range(m):
            print(res[j], end=' ')
        print()
        cnt+=1
    else:
        for i in range(s, n+1): #range의 범위는 트리의 가지(자식) 수를 의미한다. i는 branch의 값을 의미한다.  
            res[L]=i
            DFS(L+1, i+1)
               

if __name__=="__main__":
    n, m=map(int, input().split())
    res=[0]*n  #res리스트 길이는 어느 정도의 깊이(레벨)를 의미한다.
    
    cnt=0
    DFS(0,1)
    print(cnt)

 

Hint

 

▶ s는 start point를 의미한다 .시작지점을 의미한다. 

 

▶ m은 뽑는 갯수를 의미하며, 2개를 뽑는 경우 깊이(L)은 2가 된다.

 

▶ for i in range(s, n+1)

      # range의 범위는 트리의 자식(가지) 수를 의미한다. 

      # i 는 branch 값을 의미한다. 

 

▶ i+1은 조합을 만들기 위한 조치이다.