[백준] 15654. N과 M (5)

문제

백준 15654. N과 M(5)  https://www.acmicpc.net/problem/15654

 

코드

n, m = map(int, input().split())
number = list(map(int, input().split()))
number.sort()
arr = []

def recur(idx):
    if len(arr) == m:
        print(*arr)
        return

    for i in number:
        if i not in arr:
            arr.append(i)
            recur(idx+1)
            arr.pop()

recur(1)

 

풀이

n, m = map(int, input().split())  # n개의 숫자 중 m개 고르기
number = list(map(int, input().split()))  # n개의 수 입력
number.sort()  # 사전 순 출력을 위해 정렬
arr = []  # 현재까지 고른 숫자를 저장할 리스트

입력받은 수들을 처리하고, 정렬해 사전 순 순열을 만들 준비를 한다.

 

def recur(idx):
    if len(arr) == m:
        print(*arr)  # m개 다 골랐으면 출력
        return

    for i in number:
        if i not in arr:  # 중복을 허용하지 않기 위해 이미 고른 숫자는 제외
            arr.append(i)  # 숫자 선택
            recur(idx + 1)  # 다음 숫자 고르러 재귀 호출
            arr.pop()  # 백트래킹 - 마지막 숫자 제거하고 다음 후보 탐색

백트래킹 함수 recur을 정의한다.

이 함수는 현재까지 선택한 수의 개수를 인자로 받아 재귀적으로 순열을 생성한다.

i not in arr: 이미 고른 숫자는 중복해서 고르지 않도록 체크한다.

arr.pop(): 하나 선택해서 재귀 호출하고, 다시 돌아와 원상복구한다.

 

recur(1)

초기값으로 recur(1)을 호출해 순열 생성을 시작한다.