백준 15649 N과M 파이썬 문제풀이 (python 완전탐색, 재귀, 백트래킹)

문제 보러가기

 

백준 N과M 파이썬 문제풀이

자연수 N과 M 이 있으면 

1~N까지 수로 길이가 M인 중복 없는 수열을 모두 구하는 문제이다.

 

제약이 많지 않아서 반복문으로도 단순히 구현할 수 있지만 

재귀함수를 사용해보자.

 

정답코드

n,m = map(int,input().split())

# m = depth
def recur(depth, lst):
    if depth == m:
        for l in lst:
            print(l,end=' ')
        print()
        return
    else:
        for i in range(1,n+1):
            if i not in lst:
                recur(depth+1, lst+[i])

recur(0, [])

첫번째 매개변수를 depth로, 두 번째는 list 로 해서

재귀함수로 순열을 구하였다.

 

list 타입을 매개변수로 전달할 때 레퍼런스를 전달하지 않도록 유의하자.