[Python | 15650] N과 M (2)

https://www.acmicpc.net/problem/15650

---

문제 설명

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.

📌 시간 제한: 1초

---

입력

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

---

출력

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

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

---

문제 접근

이 문제를 처음 보면 중복 없이 M개를 선택해야 한다는 점에서 "N과 M (1)"과 비슷해 보일 수 있다. 하지만, 이번 문제에서는 순서가 중요하지 않다. 즉, [1,2]와 [2,1]은 같은 경우로 간주된다. 따라서, 순열(Permutation)이 아니라 조합(Combination) 문제임을 알 수 있다.

 

"N과 M (1)" 문제와 개념적으로 연결되므로, 먼저 "N과 M (1)" 문제를 이해하면 이번 문제를 더 쉽게 접근할 수 있다.
(N과 M (1) 문제 풀이가 궁금하다면 여기를 참고)

 

예를 들어, N=3, M=2일 때 가능한 경우를 나열하면 다음과 같다.

1 → 2
1 → 3
2 → 3

 

이 과정을 백트래킹 탐색 트리로 나타내면 다음과 같다.

dfs(1)   # 시작
 ├── 1 선택 → dfs(2)
 │     ├── 2 선택 → dfs(3) → [1 2] 출력 → 돌아감 (백트래킹)
 │     ├── 3 선택 → dfs(4) → [1 3] 출력 → 돌아감 (백트래킹)
 │
 ├── 2 선택 → dfs(3)
 │     ├── 3 선택 → dfs(4) → [2 3] 출력 → 돌아감 (백트래킹)
 │
 ├── 3 선택 → dfs(4) (더 이상 선택할 수 없음)

---

구현

코드 1 : 백트래킹

이 문제에서는 순서가 중요하지 않은 조합(Combination)을 구해야 하므로, 기존의 "N과 M (1)" 방식과는 접근 방식이 다르다.

 

1. 중복 방지 방식이 다르다.
   • "N과 M (1)"에서는 visited 배열을 사용해 중복 여부를 체크했다.
   • 하지만 "N과 M (2)"에서는 start 변수를 활용하여 이미 선택한 숫자보다 작은 숫자는 선택하지 않도록 한다.
2. 탐색 범위가 다르다.
   • "N과 M (1)"에서는 모든 숫자를 선택할 수 있었지만,
   • "N과 M (2)"에서는 현재 숫자보다 큰 숫자만 선택하도록 for i in range(start, n+1)로 설정하여 오름차순을 자동으로 유지한다.
3. 결과적으로, visited 배열 없이도 조합을 구할 수 있다.
   • 백트래킹 시 이전 숫자보다 작은 숫자는 선택되지 않으므로 중복을 방지할 필요가 없다.

따라서 dfs(1)을 호출하여 탐색을 1부터 시작하고, start 변수를 활용해 이전보다 작은 숫자는 선택되지 않도록 한다.
이렇게 하면 조합을 구하는 과정에서 자동으로 오름차순이 유지되며, 중복 없이 탐색할 수 있다.

 

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

def dfs(start):
    if len(arr) == m:
        print(*arr)
        return

    for i in range(start, n+1):  # 이전보다 큰 숫자만 선택하도록 start 설정
        arr.append(i)
        dfs(i + 1)  # 다음 숫자는 현재 숫자보다 커야 함
        arr.pop()  # 백트래킹

dfs(1)  # 1부터 탐색 시작

 

코드 2 : itertools.combinations

이 문제는 서로 다른 숫자의 조합을 구하는 문제이므로, Python의 itertools.combinations을 활용하면 더 간단하게 해결할 수 있다.

from itertools import combinations

n, m = map(int, input().split())

for comb in combinations(range(1, n+1), m):
    print(*comb)