조합 구하기

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

풀이1

• 조합에서는 앞에 있는 원소들이 뒤에 있는 원소들보다 작아야하므로 그 특성을 이용했습니다.

from sys import stdout


def check_big(a):
    for i in range(1, len(a)):
        if a[i - 1] >= a[i]:
            return False
    return True


def dfs(a):
    global cnt
    if a == m:
        if check_big(lst):
            stdout.write(" ".join(lst) + "\n")
            cnt += 1
    else:
        for i in range(1, n + 1):
            lst[a] = str(i)
            dfs(a + 1)


cnt = 0
n, m = map(int, input().split())
lst = [0] * m
dfs(0)
print(cnt)

• 위의 check_big은 전에 나온 원소보다 큰 원소만 출력하도록 만드는 플래그 함수입니다.

풀이2

• 플래그 함수는 추가적으로 시간복잡도가 필요하기 때문에 아래와 같은 방식을 사용하는게 훨씬 나은 것 같습니다.
• 여기서 주목해야하는 것은 DFS 함수의 인자입니다.
• 인자를 넣음으로써 다음에 넣어야 하는 것들만 넣을 수 있게 만들었습니다.

from sys import stdout


def dfs(a, b):
    global cnt
    if a == m:
        stdout.write(" ".join(lst) + "\n")
        cnt += 1
    else:
        for i in range(b, n + 1):
            lst[a] = str(i)
            dfs(a + 1, i + 1)


cnt = 0
n, m = map(int, input().split())
lst = [0] * m
dfs(0, 1)
print(cnt)

풀이3

• 라이브러리에서 제공되는 itertools의 combinations를 사용하는 것입니다.
• 사용방법은 아래와 같습니다.

from sys import stdout


def dfs(a, b):
    global cnt
    if a == m:
        stdout.write(" ".join(lst) + "\n")
        cnt += 1
    else:
        for i in range(b, n + 1):
            lst[a] = str(i)
            dfs(a + 1, i + 1)


cnt = 0
n, m = map(int, input().split())
lst = [0] * m
dfs(0, 1)
print(cnt)