[파이썬 알고리즘 문제풀이] - Section6 / 완전탐색 (백트랙킹, 상태트리와 CUT EDGE)-DFS(깊이우선탐색)기초 - 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.text", "rt")

n, m = map(int, input().split())
res = [0] * m
cnt = 0
def DFS(L, start): #현재 레벨과 어디서부터 시작해야하는지 들어와
    global cnt
    if L == m: #M개 다 뽑은 경우 종료조건
        for x in res:
            print(x, end = " ")
        print()
        cnt += 1
    else:
        for i in range(start, n+1):
            res[L] = i #이번 단계에서 i사용
            DFS(L+1, i+1)
            
DFS(0,1)      
print(cnt) 

코멘트

조합 구하기 문제. 이 유형을 토대로 응용한 문제들 많이 나온다. 그러니 해당 코드 이해하고 잘 풀어 나가야 해 !!