백준 15649-N과 M(1)

문제

알고리즘 분류)

• 백트래킹

풀이

백트래킹 입문 문제로 나와있는 것이다
1부터 N까지 자연수 중 M개를 중복없이 고르면 된다 -> 6! / 3! = 6P3

소스코드

python)

# 재귀함수 이용
def dfs(end, max_depth,stack):
    for i in range(1,end+1):
        if i in stack:
            continue
        else:
            stack.append(i)

        if len(stack) == max_depth:
            print(*stack)
        else:
            dfs(end,max_depth,stack)
        
        stack.pop()
        

end, max_depth = map(int, input().split())
stack = []
dfs(end,max_depth,stack)

stack[] 안에 수가 이미 들어있다면 건너띄고 그렇지 않으면 stack[]에 넣어준다

만약 stack[]이 뽑으려는 갯수(M)를 만족했다면 print해준다

그렇지 않으면 재귀호출을 시도해 M에 만족할때 까지 반복한다

for문이 끝나면 가장마지막의 원소를 pop해준다

# permutations 사용
from itertools import permutations
array = list(map(str, range(1,9)))

N, M = map(int, input().split())
array = array[0:N]

result=list(map(' '.join, permutations(array, M)))

for i in result:
    print(i)

파이썬 itertools에서 제공하는 함수로 손쉽게 구현할 수 있다