[파이썬(Python)] 백준 15664번 N과 M (10)

 

 

백준 15664번: N과 M (10)

문제 바로 가기

---

📌 문제

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

N개의 자연수 중에서 M개를 고른 수열
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 $A_1 ≤ A_2 ≤ ... ≤ A_{K-1} ≤ A_K$를 만족하면, 비내림차순이라고 한다.

입력

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

출력

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

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

 

이 문제는 N개의 자연수가 주어졌을 때 M개의 숫자를 선택하여 만들 수 있는 모든 수열을 찾는 문제입니다. 단, 아래의 조건을 반드시 만족해야 합니다. 

 

 

 

 

 

✅ 조건

 

 

1. 비내림차순(오름차순)으로 정렬된 수열이어야 합니다.

 

즉, 이전에 선택한 숫자보다 같거나 큰 숫자만 다음에 선택할 수 있습니다.  예를 들어 (1, 2)는 가능하지만 (2, 1)은 불가능합니다. 

 

 

 

2. 같은 숫자가 여러 번 등장할 수 있습니다.

 

예를 들어, 입력값이 1 1 2 2 라면 같은 숫자를 선택하는 것이 허용됩니다. 

 

 

 

3. 중복되는 수열을 여러 번 출력하면 안 됩니다.

 

예를 들어 (1, 2)와 (2, 1)은 다르지만 (1, 2)가 여러 번 출력되는 것은 허용되지 않습니다. 즉, 같은 수열은 한 번만 출력해야 합니다. 

 

 

 

4. 결과는 사전순(오름차순)으로 출력해야 합니다.

 

이를 위해 입력값을 먼저 정렬한 후 탐색을 수행해야 합니다. 

 

 

 

 

 

 

 

 

 

 

📚 관련 개념

 

 

 

1️⃣ 백트래킹(Backtracking)

 

 

백트래킹은 모든 경우의 수를 탐색하면서 특정 조건을 만족하지 않으면 더 깊이 탐색하지 않고 되돌아오는(Backtrack) 방식입니다. 

 

 

이 문제는 N개의 자연수가 주어졌을 때 M개의 숫자를 선택하여 만들 수 있는 모든 수열을 찾는 문제입니다. 하지만 무작정 모든 경우를 탐색하면 중복된 결과가 나올 수 있고 불필요한 탐색이 많아질 수 있습니다. 따라서 백트래킹을 사용해 중복을 방지하고 불필요한 탐색을 줄여야 합니다. 

 

 

 

 

 

 

 

 

 

 

💡 해결 방법

 

 

 

1️⃣ 입력된 숫자들을 먼저 정렬합니다. 

 

사전순(오름차순)으로 탐색해야 하므로 먼저 정렬해놓으면 자연스럽게 사전순으로 정렬된 수열을 만들 수 있습니다.

 

 

 

 

2️⃣ 백트래킹을 이용하여 수열을 하나씩 만듭니다.

 

시작 인덱스 start를 유지하면서 현재까지 선택한 숫자보다 같거나 큰 숫자만 추가할 수 있도록 합니다. 이를 통해 비내림차순(오름차순) 조건을 만족할 수 있습니다.

 

 

 

 

3️⃣ 중복되는 수열을 방지합니다.

 

정렬된 배열에서 같은 숫자가 연속으로 등장하면 두 번째 이후의 동일 숫자는 건너뜁니다. 이를 위해 현재 인덱스의 숫자가 직전 숫자와 동일하면 선택을 건너뛰도록 합니다. 이렇게 하면 같은 숫자가 같은 깊이에서 여러 번 선택되는 것을 방지할 수 있습니다. 

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

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

    for i in range(start, n):
        if i > start and nums[i] == nums[i - 1]:
            continue
        backtrack(i + 1, seq + [nums[i]])

n, m = map(int, input().split())
nums = sorted(list(map(int, input().split())))
backtrack(0, [])

 

Algorithm/백준/Silver/15664. N과 M （10） at main · kuun1000/Algorithm