[파이썬(Python)] 백준 15655번 N과 M (6)

 

 

백준 15655번: N과 M (6)

문제 바로 가기

---

📌 문제

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

N개의 자연수 중에서 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

이 문제는 주어진 N개의 자연수에서 M개를 선택하여 오름차순으로 정렬된 수열을 구하는 문제입니다. 

 

 

 

✅ 조건

• 선택한 수열은 오름차순이어야 합니다.
• 중복된 수열을 출력하지 않습니다.
• 결과는 사전순(오름차순)으로 출력합니다.

 

 

즉, N개의 숫자 중에서 M개를 선택하는 조합(Combination) 문제이며 이를 백트래킹(Backtracking)을 활용하여 해결할 수 있습니다. 

 

 

 

 

 

 

 

 

 

 

📚 관련 개념

 

 

 

1️⃣ 조합(Combination)

 

 

N개의 숫자 중에서 M개를 선택하는 문제로, 선택한 숫자의 순서는 중요하지 않습니다. 

 

예를 들어, [1, 2, 3]에서 M = 2라면 (1, 2)와 (2, 1)은 같은 조합이므로 오름차순인 (1, 2)만 선택히야 합니다. 

 

이 문제에서는 한 번 선택한 숫자는 다시 선택할 수 없으며, 반드시 이전 숫자보다 큰 숫자만 선택해야 합니다.

 

 

 

 

 

2️⃣ 백트래킹(Backtracking)

 

 

백트래킹은 모든 경우의 수를 탐색하면서도 조건을 만족하지 않는 경우는 즉시 제외하는 기법입니다. 

 

이 문제에서는 M개의 숫자를 선택할 때까지 재귀적으로 탐색하며 조건을 만족하는 조합을 찾으면 출력합니다.

 

 

 

 

 

 

 

 

 

 

💡 해결 방법

 

 

 

1️⃣ 입력값 정렬

 

먼저, 입력으로 주어진 N개의 숫자를 오름차순으로 정렬합니다.

 

이렇게 하면 조합을 생성할 때 자동으로 사전순으로 정렬된 상태에서 탐색할 수 있습니다.

 

 

 

 

 

2️⃣ 백트래킹 함수 backtrack 구현

 

 백트래킹을 사용하여 M개의 숫자가 선택될 때까지 탐색합니다.

 

• 현재 선택한 숫자 개수가 M개가 되면 출력합니다.
• 숫자를 선택할 때 이전 숫자보다 큰 숫자만 선택하도록 start 인덱스를 활용합니다.

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

def backtrack(start, path):
    if len(path) == m:
        print(*path)
        return

    for i in range(start, n):
        backtrack(i+1, path+[nums[i]])

n, m = map(int, input().split())
nums = sorted(list(map(int, input().split())))

backtrack(0, [])