[Python] 15657 N과 M(8)

문제

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

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

입력

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

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

출력

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

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

문제 풀이

A. 접근

중복을 허용하며 비내림차순이다. 그래서 이전에 나온 값이 다시 사용될 수 있는 것이다. 굳이 방문 테이블을 만들지 않고 재귀 구조를 작성하는 것이 답이다. 중복을 허용하지 않는다면 방문 테이블을 만들어서 방문 여부를 체크하여 풀이한다.

B. 코드 분석

전체 코드

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

arr = []

def bt(idx, cnt):
    if cnt == m:
        print(*arr)
        return

    for i in range(idx, len(num)):
        arr.append(num[i])
        bt(i, cnt + 1)
        arr.pop()

bt(0, 0)

B-1. 준비

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

arr = []

비내림차순이기 때문에 미리 sorted 함수로 정렬된 리스트를 반환 받는다. arr은 출력에 사용할 리스트이다.

B-2. 풀이

def bt(idx, cnt):
    if cnt == m:
        print(*arr)
        return

    for i in range(idx, len(num)):
        arr.append(num[i])
        bt(i, cnt + 1)
        arr.pop()

bt(0, 0)

비내림차순이며 중복을 허용하기 때문에 각 수열을 구할 때 반복문을 사용할 때 시작 인덱스를 이전 함수로부터 받아와서 설정한다.

예를 들어,

4 4
9 8 7 1

의 입력을 받았다고 했을 때,

# arr = [1, 7, 8]
for i in range(3, 4):
    arr.append(num[i])
    bt(i, cnt + 1)
    arr.pop()

for i 를 통해 arr에 저장되는 수는 8로 arr = [1, 7, 8, 8]이 되는 것이다.

총평

조금 더 어려운 백트래킹을 해도 괜찮을 것 같다 :)