[파이썬(Python)] 백준 15657번 N과 M (8)

 

 

백준 15657번: N과 M (8)

문제 바로 가기

---

📌 문제

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

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

입력

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

출력

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

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

이 문제에서는 N개의 서로 다른 자연수가 주어지고, 이 중에서 M개의 숫자를 선택하여 수열을 만들어야 합니다. 단, 다음  조건을 반드시 만족해야 합니다.

 

 

 

 

 

1️⃣ 같은 숫자를 여러 번 선택할 수 있습니다.

 

예를 들어, 숫자 2 3 5 가 주어졌다면 2 2 2, 3 3 3, 5 5 5 와 같은 수열도 만들 수 있습니다.

 

 

 

 

2️⃣ 선택한 숫자들은 비내림차순이어야 합니다.

 

즉, 앞에 있는 숫자가 뒤에 있는 숫자보다 커지면 안 됩니다. 예를 들어, 1 2 2 는 가능하지만 2 1 3 은 불가능합니다.

 

 

 

 

3️⃣ 출력되는 수열들은 사전순(오름차순)으로 정렬된 형태여야 합니다.

 

입력으로 주어진 숫자들이 정렬되지 않은 상태로 들어올 수도 있으므로, 먼저 정렬한 후 수열을 만들어야 합니다. 

 

 

 

 

 

 

 

 

 

 

🔍 예제 이해

 

 

입력 예시

4 2
9 8 7 1

위 입력에서는 4개의 숫자 9, 8, 7, 1 이 주어졌고, 이 중에서 2개를 선택하여 만들 수 있는 모든 수열을 찾아야 합니다. 

 

 

 

 

 

가능한 출력

1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9

위와 같이 모든 수열이 오름차순을 유지하고 있으며 같은 숫자를 여러 번 선택할 수 있음을 확인할 수 있습니다. 또한 수열들을 오름차순(사전순)으로 정렬된 형태로 출력됩니다. 

 

 

 

 

 

접근 방법

 

 

이 문제를 해결하기 위해서는 수열을 만드는 과정에서 조건을 만족하도록 탐색하는 방법이 필요합니다. 이를 효과적으로 구현하기 위해 백트래킹(Backtracking) 기법을 사용할 수 있습니다.

 

 

 

 

 

 

💡 아이디어

 

 

1️⃣ 어떤 방식으로 수열을 만들까?

 

 

N개의 자연수 중에서 M개를 선택하는 모든 경우를 찾아야 합니다. 하지만, 조건을 만족하는 경우만 고려해야 하므로 다음과 같은 규칙을 따라야 합니다.

 

• 숫자를 중복해서 선택할 수 있습니다.
  • 즉, 이전에 선택한 숫자를 또 선택하는 것이 가능해야 합니다.
  • 예를 들어, 숫자 1 2 3 이 있다면 1 1, 2 2, 3 3 과 같은 수열이 가능해야 합니다.

 

 

• 수열을 비내림차순이어야 합니다.
  • 즉, 수열의 앞쪽 숫자가 뒤쪽 숫자보다 커지는 경우는 허용되지 않습니다.
  • 예를 들어, 1 2 는 가능하지만 2 1은 불가능합니다.

 

 

• 출력되는 순서는 사전순(오름차순)이어야 합니다.
  • 입력으로 주어지는 숫자들이 정렬되지 않은 상태일 수 있으므로, 먼저 정렬한 후 탐색을 시작하면 출력 순서를 자동으로 맞출 수 있습니다.

 

 

 

 

 

2️⃣ 비내림차순을 유지하는 방법

 

 

비내림차순을 유지하기 위해 이전에 선택한 숫자보다 작은 숫자는 다시 선택할 수 없도록 하면 됩니다.

 

예를 들어 숫자 1 2 3 4 가 주어졌다고 가정하면 

• 1 을 선택한 경우, 이후에는 1, 2, 3, 4 를 선택할 수 있습니다.
• 2 를 선택한 경우, 이후에는 2, 3, 4 만 선택할 수 있습니다.
• 3 을 선택한 경우, 이후에는 3, 4 만 선택할 수 있습니다.
• 4 를 선택한 경우, 이후에는 4 만 선택할 수 있습니다.

 

 

이렇게 하면 자동으로 비내림차순 조건을 만족하는 수열만 생성할 수 있습니다.

 

 

 

 

 

3️⃣ 백트래킹을 활용한 완전 탐색

 

 

모든 가능한 수열을 찾는 문제이므로 백트래킹(Backtracking) 기법을 활용할 수 있습니다. 백트래킹을 통해 현재 선택한 숫자들을 저장하면서 조건을 만족하지 않으면 즉시 되돌아가면서 불필요한 경우를 배제하는 탐색 방법입니다.

 

 

 

1. 입력된 숫자들을 먼저 오름차순으로 정렬하여 사전순 출력을 자동으로 맞춥니다. 

 

2. 백트래킹 함수(backtrack)를 사용하여 하나의 숫자를 선택한 후, 이전 숫자보다 작은 숫자는 제외하면서 탐색을 진행합니다.

 

3. M개의 숫자를 선택하면 해당 수열을 출력하고 탐색을 종료합니다.

 

4. 모든 경우를 탐색할 때까지 위 과정을 반복합니다. 

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

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

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



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

backtrack(0, [])