[Python] 백준 15649 N과 M

🧑‍💻 [Python] 백준 15649 N과 M

Silver 3 - Backtracking

쉽게 itertools의 permutations를 사용해서 풀 수 있는 문제다

하지만 Backtracking을 공부하고 싶어서 풀었던 문제다

• 기본적으로 if len(l) == M: 을 통해서 재귀 함수의 base case를 만든다
  • 안 만들면 무한 루프
• 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 dfs()를 다시 돈다
• 그리고 l.pop()을 해야, 리스트에 숫자가 사라지고, 다른 경우의 수를 넣을 수 있다

---

 

코드

 

백트래킹 사용

N, M = map(int, input().split())

l = []

def dfs():

    if len(l) == M:
        print(" ".join(map(str, l)))
        return

    for num in range(1, N + 1):
        if num not in l:
            l.append(num)
            dfs()
            l.pop()

dfs()

 

permutations 사용

from itertools import permutations

N, M = map(int, input().split())

num_list = [num for num in range(1, N + 1)]

for nums in permutations(num_list, M):
    print(" ".join(map(str, list(nums))))