[Python] 15655 N과 M(6)

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

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

출력

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

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

문제 풀이

A. 접근

이번 문제는 15652 N과 M(4) 문제를 응용한 문제이다.

오름차순이며, 순서를 고려하지 않고 출력해야 한다.

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 + 1, cnt + 1)
        arr.pop()

bt(0, 0)

B-1. 준비

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

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 + 1, cnt + 1)
        arr.pop()

bt(0, 0)

재귀를 들어가기 전에 for 문에서 idx부터 시작하는 것에 주목을 하자. idx는 주어진 배열에서 수를 받을 위치를 지정한다. 예를 들어

4 2
9 8 7 1

이렇게 입력이 주어지면

for i in range(0, 4):

이런 반복문이 시작이 되고, arr = [1]이 되며 bt(1, 1)로 함수를 다시 실행한다.

for i in range(1, 4):

이후에 반복문이 위와 같이 설정이 되며, [1, 7, 8, 9] 에서 [7, 8, 9]만 반복문에 사용하는 셈이 된다. 이것을 쭉 반복한다.

이렇게 하는 이유는 오름차순으로 출력해야 되기 때문이며, 미리 정렬을 해두었기 때문이다.

총평

백트래킹에 대한 감이 조금 잡히고 있다.