[백준] 15650번 - Silver 3 N과 M (2), 파이썬 코드

solved.ac의 Class 4 문제 중 N과 M(2) 문제이다.

 

1부터 비내림차순으로 내려가야 하는 특징 때문에 재귀 DFS 문제라는 것을 알 수 있다.

"1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열"이라는 문제의 특징이 있으니 조심하자.

 

해결했던 코드는 다음과 같다.

 

import sys
global n, m

lst = []

def dfs(num):
    # 리스트의 개수가 m과 같아지면 return
    if len(lst) == m:
        print(" ".join(map(str, lst)))
        return
    for i in range(num+1, n+1):
        lst.append(i)
        dfs(i)
        lst.pop()

if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    dfs(0)