[백준] 15650 N과 M(2)

🌭 문제 설명

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이M개를 고른 수열

• 고른 수열은 오름차순이어야 한다.

---

🍗 제한 사항

---

🎁 입출력 예시

• 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

• 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

• 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

😎 나의 풀이

from itertools import combinations # 순열 라이브러리

# 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 , 오름 차순
N, M = map(int, input().split()) # N : 4 , M : 2

nums = list(range(1,N+1)) 
perm = list(combinations(nums, M))
sorted(perm) # 오름 차순

for p in perm:
    print(*p) # 튜플 p의 요소를 unpack해서 공백으로 구분해 출력
    

1. 순열을 써서 풀었다.
2. 1부터 N까지 배열을 만들고 만든 배열을 가지고 M개를 순열로 뽑는다.
3. 오름차순 정렬
4. 뽑은 요소들은 튜플의 형태이기 때문에 *을 붙여서 출력한다.

---

🧵 다른 풀이

def backtracking(arr):
    if len(arr) == m:
        print(' '.join(map(str, arr)))
        return
    for i in range(arr[-1] if arr else 1, n + 1):
        if i not in arr:
            arr.append(i)
            backtracking(arr)
            arr.pop()


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

1. 백트래킹으로 푼 풀이

---

• 다른 풀이를 보니 dfs나 백트래킹으로도 풀 수 있던 문제였다.