[DFS] 조합
조합 구하기
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)
Author And Source
이 문제에 관하여([DFS] 조합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sparkbosing/DFS-조합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)