[백준] 15649 파이썬(python) : N과 M (1) - (permutations이용)

15649번 : N과 M (1)

 

 

 

n, m = map(int, input().split())
answer = []

def backTracking(depth):
    if m == depth:
        print(" ".join(map(str, answer)))
        return
    for i in range(1, n+1):
        if i in answer: #1
            continue
        answer.append(i)
        backTracking(depth+1)
        answer.pop()

backTracking(0)

 

 

15651번 문제와 비슷한 문제다. 재귀함수로 순환하는 루틴도 비슷하다. 다른 점이 있다면 출력할때 같은 정수가 2번 나오면 안된다는 것이다. 그래서 continue문을 달아줬다.

#1 : 1 2 3 4 또는 1 2 4 3 처럼 나와야하기 때문에 answer에서 i와 같은 원소가 있으면 반복문은 건너뛴다. 

 

 

다른풀이)

순열을 이용해서 푸는 방법이 있다.

import sys, itertools
n, m = map(int, sys.stdin.readline().split())
arr = [ str(i) for i in range(1, n+1) ] #1
for i in itertools.permutations(arr, m): #2
    print(' '.join(i)) #3

 

 

#1 : 1부터 n까지의 숫자를 담는 리스트 생성

#2 : 조합을 이용해 arr중에서 m개의 숫자를 선택

#3 : 문자열로 생성했으니까 join함수를 이용해서 빈칸을 사이에 두고 묶어서 출력한다

 

 

아래는 백트래킹 위는 순열

 

 

import sys
from itertools import permutations
n, m = map(int, sys.stdin.readline().split())
numbers = list(range(1, n+1))
for i in permutations(numbers, m):
    print(*i)

 

 

---

15651번 : N과 M (3)