[파이썬(Python)] 백준 15650번 N과 M (2)

 

 

백준 15650번: N과 M (2)

문제 바로 가기

---

📌 문제

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

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

 

 

 

 

 

 

 

 

📝 아이디어

 

 

문제 분석

 

이 문제는 자연수 N과 M이 주어졌을 때, 1부터 N까지의 자연수 중에서 M개의 수를 선택하여 만들 수 있는 모든 수열을 구하는 문제입니다. 주어진 조건은 다음과 같습니다.

 

• 중복 없이 M개의 수를 선택해야 합니다.
• 선택된 수열은 오름차순으로 정렬된 형태여야 합니다.
• 결과는 사전 순으로 출력해야 합니다. 

 

 

 

 

 

 

 

아이디어

 

문제의 조건을 보면 조합(Combination)을 생성하는 문제임을 알 수 있습니다. 따라서 백트래킹을 활용하면 효율적으로 해결할 수 있습니다. 

 

 

 

1. 백트래킹(Backtracking) 활용

 

백트래킹은 현재 상태에서 가능한 모든 경로를 따라 탐색하는 방법입니다. 원하는 조건을 만족하지 않는 경우 더 이상 탐색을 진행하지 않고 이전 상태로 되돌아가는(Backtracking) 방법입니다. 

 

이 문제에서는 오름차순이라는 조건이 있으므로, 현재 선택한 숫자보다 더 큰 숫자만 선택하도록 탐색을 진행합니다. 

 

 

 

2. 탐색 과정 

 

1. 1부터 시작하여 숫자를 선택합니다. 

2. 선택한 숫자보다 큰 숫자만 다음에 선택할 수 있습니다. 

3. 선택한 숫자가 m개가 되면 출력합니다. 

4. 탐색을 끝낸 후에는 이전 상태로 돌아가서 다른 선택지를 탐색합니다. 

 

 

 

3. 구현 방법

 

• 재귀 함수를 활용하여 숫자를 하나씩 선택하며 탐색을 진행합니다.
• 현재 선택한 숫자보다 더 큰 숫자만 선택하도록 시작 인덱스를 조정합니다.
• 길이가 m이 되면 해당 조합을 출력합니다.
• 선택이 끝나면 백트래킹을 사용하여 이전 상태로 되돌아갑니다.

 

이 방식으로 탐색하면 자연스럽게 오름차순 정렬이 유지되며, 사전 순으로 결과를 출력할 수 있습니다. 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

def backtrack(start, path, n, m):
    if len(path) == m:
        print(" ".join(map(str, path)))
        return
    
    for i in range(start, n + 1):
        backtrack(i + 1, path + [i], n, m)

n, m = map(int, input().split())
backtrack(1, [], n, m)

 

Algorithm/백준/Silver/15650. N과 M （2） at main · kuun1000/Algorithm