[파이썬(Python)] 백준 15665번 N과 M (11)

 

 

백준 15665번: N과 M (11)

문제 바로 가기

---

📌 문제

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

N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

입력

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

출력

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

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

 

이 문제는 다음과 같은 조건을 만족하는 길이가 M인 수열을 구하는 문제입니다.

 

 

 

✅ 조건

• 주어진 N개의 자연수 중에서 M개를 선택하여 수열을 만듭니다.
• 같은 숫자를 여러 번 선택해도 됩니다. → 중복 허용
• 결과로 나오는 수열은 중복되면 안 됩니다. 
• 수열은 사전순(오름차순)으로 출력해야 합니다.

 

 

 

 

 

 

 

 

 

 

💡 아이디어

 

 

 

이 문제를 해결하기 위해 백트래킹(Backtracking) 기법을 사용합니다. 백트래킹이란 모든 경우의 수를 탐색하면서 조건에 맞지 않으면 되돌아가는 방식입니다. 

 

 

 

 

1️⃣ 입력받은 숫자 리스트를 정렬

• 먼저 입력받은 숫자 리스트를 정렬하면 자동으로 사전순으로 출력할 수 있습니다. 
• 따라서 출력할 때 따로 정렬할 필요가 없습니다. 

 

 

 

 

2️⃣ 백트래킹을 사용하여 길이가 M인 수열을 생성

• 처음에는 빈 리스트([])에서 시작하여 하나씩 숫자를 추가해 나갑니다.
• 숫자를 추가하다가 길이가 M이 되면 출력하고 종료합니다. 

 

 

 

 

3️⃣ 같은 깊이에서 중복 숫자가 다시 선택되지 않도록 함

• prev_num 변수를 사용하여 같은 깊이에서 같은 숫자가 중복 선택되지 않도록 합니다. 

 

 

 

 

 

 

 

 

 

 

🚀 동작 과정

 

 

 

예제 입력

4 2
9 7 9 1

 

 

 

 

1️⃣ 입력값 정렬

 

입력값 [ 9, 7, 9, 1 ] 을 오름차순 정렬하면 [ 1, 7, 9, 9 ] 가 됩니다. 이제 이 정렬된 리스트를 사용해 수열을 구성합니다. 

 

 

 

2️⃣ 백트래킹 탐색 과정

 

 

🔸 초기 상태 (backtrack([])) → 아직 아무 숫자도 선택하지 않은 상태

• 선택 가능한 숫자: [ 1, 7, 9 ]
• prev_num = -1 (아직 선택한 숫자가 없기 때문에 중복 방지 변수 없음)
• 첫 번째 숫자를 선택해야 함 → 1부터 시작

 

 

 

🔸 첫 번째 숫자 선택 (backtrack([1])) → 수열의 첫 번째 숫자로 1을 선택

• 선택 가능한 숫자: [1, 7, 9] (중복 허용)
• prev_num = -1 (아직 같은 깊이에서 중복된 숫자가 없음)
• 새로운 재귀 호출 → backtrack([1])

 

 

 

🔸 두 번째 숫자 선택 (backtrack([1, X])) → 두 번째 숫자를 선택해야 함

• 선택 가능한 숫자: [1, 7, 9]
• 이전 숫자(prev_num)와 비교하여 중복 방지
  • 1 선택 가능 → backtrack([1, 1])
  • 7 선택 가능 → backtrack([1, 7])
  • 9 선택 가능 → backtrack([1, 9])

 

길이가 M = 2이므로 각각 출력 후 종료

1 1
1 7
1 9

 

 

 

🔸 다음 숫자 선택 (backtrack([7])) → 첫 번째 숫자로 7을 선택한 경우

• 선택 가능한 숫자: [1, 7, 9]
• prev_num = 1 (이전 단계에서 1이 이미 사용됨)
• 새로운 재귀 호출 → backtrack([7])
• 두 번째 숫자 선택 (backtrack([7, X]))
  • 1 선택 가능 → backtrack([7, 1])
  • 7 선택 가능 → backtrack([7, 7])
  • 9 선택 가능 → backtrack([7, 9])

 

길이가M = 2이므로 각각 출력 후 종료

7 1
7 7
7 9

 

 

 

🔸 다음 숫자 선택 (backtrack([9])) → 첫 번째 숫자로 9을 선택한 경우

• 선택 가능한 숫자: [1, 7, 9]
• prev_num = 1 (이전 단계에서 1이 이미 사용됨)
• 새로운 재귀 호출 → backtrack([9])
• 두 번째 숫자 선택 (backtrack([9, X]))
  • 1 선택 가능 → backtrack([9, 1])
  • 7 선택 가능 → backtrack([9, 7])
  • 9 선택 가능 → backtrack([9, 9])

 

길이가 M = 2이므로 각각 출력 후 종료

9 1
9 7
9 9

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

def backtrack(seq):
    if len(seq) == m:
        print(*seq)
        return
    
    prev = -1

    for i in range(n):
        if nums[i] == prev:
            continue
        prev = nums[i]
        backtrack(seq + [nums[i]])

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