[파이썬(Python)] 백준 15666번 N과 M (12)

 

 

백준 15666번: N과 M (12)

문제 바로 가기

---

📌 문제

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

N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

출력

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

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

이 문제는 N개의 자연수 중에서 M개를 선택하여 만들 수 있는 모든 수열을 구하는 문제입니다. 단, 다음의 조건을 반드시 만족해야 합니다.

 

 

✅ 조건

• 같은 숫자를 여러 번 선택하는 것이 허용됩니다.
• 비내림차순이어야 합니다. 
• 중복된 수열은 여러 번 출력하면 안 됩니다.
• 사전순으로 증가하는 순서로 정렬하여 출력해야 합니다. 

 

 

 

 

 

 

 

 

 

 

🔍 예제 살펴보기

 

 

📌예제 1

3 1
4 4 2

숫자 4 4 2 중에서 1개를 선택해야 합니다. 중복된 숫자를 제거하고 정렬하면 2 4 가 됩니다.

 

 

 

📌 출력 1

2
4

한 개의 숫자를 선택하는 경우의 수이므로 중복을 제거한 후 2와 4만 선택할 수 있습니다. 

 

 

 

 

 

📌예제 2

4 2
9 7 9 1

숫자 9 7 9 7 중에서 2개를 선택해야 합니다. 중복을 제거하고 정렬하면 1 7 9 가 됩니다.

 

 

 

📌 출력 2

1 1
1 7
1 9
7 7
7 9
9 9

비내림차순을 유지해야 하므로 다음과 같이 6가지 경우가 나옵니다. 

• 1을 선택하면 1 1, 1 7, 1 9
• 7을 선택하면 7 7, 7 9
• 9를 선택하면 9 9

 

 

 

 

 

📌예제 3

4 4
1 1 2 2

숫자 1 1 2 2 중에서 4개를 선택해야 합니다. 중복을 제거하고 정렬하면 1 2 가 됩니다.

 

 

 

📌 출력 3

1 1 1 1
1 1 1 2
1 1 2 2
1 2 2 2
2 2 2 2

길이가 4인 수열을 만들어야 하기 때문에 1과 2를 여러 번 선택하는 조합을 찾습니다.

비내림차순을 유지하면서 만들 수 있는 조합은 위와 같습니다. 

 

 

 

 

 

 

 

 

 

 

💡 해결 방법

 

 

이 문제를 해결하기 위해 백트래킹(Backtracking) 기법을 사용합니다. 백트래킹이란 모든 가능한 경우를 탐색하면서 불필요한 경우는 미리 가지치기(Pruning)하는 알고리즘입니다. 

 

이 문제에서는 M개의 숫자를 선택하는 모든 경우를 찾되 조건을 만족하는 경우만 출력해야 합니다. 

 

 

 

 

 

⭐ 조건 분석

 

1️⃣ 숫자는 여러 번 선택 가능

• 예를 들어, 숫자가 1 7 9 일 때 1 1 또는 7 7 처럼 같은 숫자를 여러 번 선택할 수 있습니다.
• 즉, 선택한 숫자를 다시 선택할 수 있도록 중복을 허용하는 방식으로 탐색해야 합니다. 

 

 

 

2️⃣ 선택한 숫자는 비내림차순이어야 함

• 비내림차순이란 앞의 숫자보다 뒤의 숫자가 크거나 같은 경우만 허용하는 것입니다,
  • 가능 ⭕: 1 1 2, 1 2 2, 7 7 9
  • 불가능 ❌: 2 1 1, 9 7 1
• 따라서 새로운 숫자를 선택할 때 이전 숫자보다 작으면 선택하지 않도록 해야 합니다.
• 이를 위해 현재 선택한 숫자의 인덱스보다 같은 위치 이상의 숫자만 탐색하도록 합니다. 

 

 

 

3️⃣ 중복되는 수열은 한 번만 출력해야 함

• 예를 들어, 입력이 4 2 이고 숫자가 9 7 9 1 일 때 중복을 제거하면 1 7 9 이므로 다음과 같은 경우만 출력해야 합니다.

1 1
1 7
1 9
7 7
7 9
9 9

• set( ) 을 사용하여 입력받은 숫자의 중복을 제거한 후 탐색하면 됩니다. 

 

 

 

 

 

 

 

 

 

 

🚀 구현

 

1️⃣ 입력된 숫자를 정렬하고 중복을 제거

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

• 중복 제거: set( ) 을 사용하여 중복된 숫자를 없앱니다.
• 정렬: sorted( ) 를 사용하여 오름차순으로 정렬합니다. → 자동으로 사전순으로 출력됩니다.

 

 

 

 

 

2️⃣ 백트래킹 함수 정의

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

• arr 리스트는 현재까지 선택한 숫자들을 저장합니다.
• 길이가 M이 되면 출력하고 종료합니다. 

 

 

 

 

 

3️⃣ 비내림차순을 유지하며 재귀 호출

for i in range(start, len(nums)): 
    backtrack(i, arr + [nums[i]])

• start 부터 탐색을 시작하므로 이전에 선택한 숫자보다 작은 숫자는 선택되지 않습니다.
• arr + [ nums [ i ] ] 를 사용하여 현재 숫자에 배열을 추가한 후 재귀 호출합니다.

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

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

    for i in range(start, len(nums)):
        backtrack(i, arr + [nums[i]])

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

backtrack(0, [])

 

Algorithm/백준/Silver/15666. N과 M （12） at main · kuun1000/Algorithm