[백준] 15649번 N과 M (1)

💡문제접근

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하는 문제인데 permutations을 이용해서 해결할 수 있었다.

💡코드(메모리 : 30616KB, 시간 : 144ms)

from itertools import permutations

N, M = map(int, input().split())
arr = [i for i in range(1, N+1)]

for i in permutations(arr, M):
    print(*i)

📌백트래킹 풀이 방법(메모리 : 31256KB, 시간 : 172ms)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
li = []

def recursive():
    if len(li) == M:
        print(" ".join(map(str, li)))
        return
    else:
        for i in range(1, N+1):
            if i not in li:
                li.append(i)
                recursive()
                li.pop()
recursive()

💡테스트케이스

입력

4 2

출력

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

• 맨 처음에 li의 길이는 M이 아니므로 if문이 실행되지 않고 내려간다. 만약 1이 li에 없다면 1을 append하고 재귀함수를 실행시켜 자기 자신을 다시 호출한다. 그 다음 다시 실행된 재귀함수가 동작되는데 이 때 1이 li에 있으므로 넘어가고 2가 들어온다. 그렇게 되면 현재 li에는 [1, 2] 두 개가 들어있으므로 조건에 만족하여 출력한다. 이런 작업을 반복한다.

💡소요시간 : 1m