조합 구하기

생성일: 2022년 2월 6일 오후 8:44

구현 코드

# 조합 구하기
import sys
sys.stdin = open("input.txt" ,"rt")

def DFS(L):
    global cnt
    if L == m:
        for x in res:
            print(x, end=' ')
        cnt += 1
        print()
    else:
        if L==0:
            for i in range(1, n+1):
                if ch[i] == 0:
                    ch[i] = 1
                    res[L] = i
                    DFS(L+1)
                    ch[i] = 0
        else:
            for i in range(res[L-1]+1, n+1):
                if ch[i] == 0:
                    ch[i] = 1
                    res[L] = i
                    DFS(L+1)
                    ch[i] = 0

if __name__ == "__main__":
    n, m = map(int, input().split())
    res = [0] * m
    ch = [0] * (n+1)
    cnt = 0
    DFS(0)
    print(cnt)

모범 답안

import sys
sys.stdin=open("input.txt", "r")
def DFS(L, s):
    global cnt
    if L==m:
        for i in range(m):
            print(res[i], end=' ')
        print()
        cnt+=1
    else:
        for i in range(s, n+1):
            res[L]=i
            DFS(L+1, i+1)
           

n, m=map(int, input().split())
res=[0]*(n+1)
cnt=0
DFS(0, 1)
print(cnt)

차이점

• 기본적인 로직은 같다.
• 내가 구현한 코드에서는 if L==0: 을 사용하여 조건문을 통해 res의 0번째 인덱스(트리의 level 0)일 때는 n까지의 수를 다 넣고 그 다음 부터는 res[L-1]+1부터 n까지의 수를 넣는 구조이다.
• 모법 답안에서는 재귀 함수의 파라미터로 s를 추가하여 L-1 인덱스에 들어 있는 값 다음 수부터 n까지의 수를 넣는 구조이다. (코드 간소화)