[백준][Python] 15666 N과 M (12)

# 문제 링크

https://www.acmicpc.net/problem/15666

 

# 문제

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

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

 

 

 

# 입력

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

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

 

# 출력

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

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

 

# 예제

예제입력	예제출력
3 1 4 4 2	2 4
4 2 9 7 9 1	1 1 1 7 1 9 7 7 7 9 9 9
4 4 1 1 2 2	1 1 1 1 1 1 1 2 1 1 2 2 1 2 2 2 2 2 2 2

 

---

# 문제 풀이

맞은코드

import sys
input=sys.stdin.readline

# 재귀호출
def back_tracking(idx) :
    # m개를 뽑으면 리턴
    if len(answer) == m :
        print_ans(answer)
        return

    for i in range(idx, length) :
        answer.append(arr[i])
        back_tracking(i)
        answer.pop()

# 출력함수
def print_ans(answer) :
    for elem in answer :
        print(elem, end=' ')
    print()

# 입력처리
n, m = map(int, input().split())
arr = sorted(list(set(map(int, input().split())))) # 비내림차순 정렬을 위한 sort와 중복 방지를 위한 set.

# 변수 선언
answer = []
length = len(arr) # 중복 제거된 리스트 길이 계산

# 재귀 호출
back_tracking(0)

 

재귀호출인데 중복을 곁들인 문제이다. 같은 수를 여러번 뽑을 수 있기에, 입력받은 리스트에서 중복되는 값을 제거해 주지 않은 채로 백트래킹을 시도하면 같은 답이 여러번 나온다. 파이썬에는 set이라는 고능한 기능이 내장되어 있어 쉽게 중복 제거가 가능하다. 이후 중복되는 원소들을 제거해서 리스트 길이도 달라지므로, 다시 리스트 길이를 계산해 준 후 재귀호출 하면 끝이다.