[Python] 15654 N과 M(5)

문제

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

• N개의 자연수 중에서 M개를 고른 수열

입력

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

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

출력

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

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

문제 풀이

A. 접근

15652 N과 M(4)

N과 M 시리즈 문제 중 하나.

이번에는 순서는 고려하지 않고 중복을 허용하지 않는다.

그래서 이번에는 내가 무엇을 선택했는지 알아야 하기 때문에 방문 테이블을 설정해서 문제를 풀었다.

B. 코드 분석

전체 코드

n, m = map(int, input().split())
num = sorted(map(int, input().split()))
is_num = [False] * n

arr = []

def bt(z):
    if z == m:
        print(*arr)
        return

    for i in range(n):
        if not is_num[i]:
            is_num[i] = True
            arr.append(num[i])
            bt(z + 1)
            is_num[i] = False
            arr.pop()

bt(0)

B-1. 준비

n, m = map(int, input().split())
num = sorted(map(int, input().split()))
is_num = [False] * n

arr = []

출력은 사전순으로 해야 해서 그냥 정렬을 사용했다. 정렬한 이후에는 그 자리에 맞는 방문 테이블을 설정한다. arr은 정답을 제출하기 위해 사용하는 리스트이다.

B-2. 풀이

def bt(z):
    if z == m:
        print(*arr)
        return

    for i in range(n):
        if not is_num[i]:
            is_num[i] = True
            arr.append(num[i])
            bt(z + 1)
            is_num[i] = False
            arr.pop()

bt(0)

저번 N과 M(4)는 비내림차순이어서 range함수에 매개변수를 두 개 사용하였는데, 이번에는 비내림차순이 아니기 때문에 n 하나만 인자로 설정했다. 이때, 수열에서 중복은 허용하지 않기 때문에 방문테이블에서 방문 처리를 해준다. 그래서 방문하지 않은 곳만 배열에 넣어준다.

if not is_num[i]:
    is_num[i] = True

그 이후에 재귀를 통해 더 깊이 들어간다. 이후에는 다시 방문을 취소하고 배열에서도 수를 빼준다.

    bt(z + 1)
    is_num[i] = False
    arr.pop()

총평

전체적인 틀은 유사하나 조건이 달라서 잘 응용해야 한다. 후후 재밌다.