[파이썬(Python)] 백준 15656번 N과 M (7)

 

 

백준 15656번: N과 M (7)

문제 바로 가기

---

📌 문제

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

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

입력

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

출력

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

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

이 문제는 주어진 N개의 자연수 중에서 M개를 선택하여 수열을 만드는 문제입니다. 

 

 

✅ 조건

• 같은 숫자를 여러 번 선택할 수 있습니다. → 하나의 숫자를 여러 번 사용할 수 있음
• 중복되는 수열을 여러 번 출력하면 안 됩니다. → 같은 조합이 반복해서 나오면 안 됨
• 수열은 사전 순(오름차순)으로 출력해야 합니다. → 작은 숫자부터 출력하도록 정렬이 필요함

 

 

 

 

 

 

 

 

 

 

📚  관련 개념

 

1️⃣ 백트래킹(Backtracking)

 

백트래킹이란 가능한 모든 경우를 탐색하면서 필요 없는 경우는 탐색하지 않고 되돌아가는(Backtrack) 방법입니다. 

 

 

예를 들어 숫자 1, 2, 3이 주어졌을 때 M = 2라면 [2, 3]과 [3, 2]는 같은 경우이므로 하나만 출력해야 합니다. 따라서, 이미 선택한 숫자보다 작은 숫자는 다시 선택하지 않도록 하여 중복된 조합이 나오지 않게 합니다.

 

 

 

 

 

 

 

 

 

 

💡 해결 방법

 

 

1️⃣ 입력된 숫자들을 오름차순으로 정렬합니다.

 

사전 순 출력을 위해 미리 정렬합니다.

 

 

 

2️⃣ 백트래킹을 사용해 수열을 생성합니다.

 

숫자를 하나씩 선택하여 수열을 만듭니다.

 

 

 

3️⃣ 길이가 M이 되면 출력합니다.

 

선택한 숫자가 M개가 되면 출력 후 종료합니다.

 

 

 

4️⃣ 같은 숫자를 여러 번 선택할 수 있도록 합니다.

 

중복 선택이 가능하므로 현재 숫자를 다시 선택할 수 있도록 합니다.

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

def backtrack(seq):
    if len(seq) == m:
        print(*seq)
        return
    
    for i in range(n):
        backtrack(seq + [nums[i]])



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

backtrack([])

 

Algorithm/백준/Silver/15656. N과 M （7） at main · kuun1000/Algorithm