[BOJ] 15657. N과 M (8)(python)

📌문제

💪아이디어

1. 비내림차순 배열
   arr[i-1] <= arr[i]로 정렬되어야 하기 때문에 입력받은 배열을 오름차순으로 정렬한다.
   

2. 부분 수열 만들기
   비내림차순으로 정렬되어있기 때문에 현재위치보다 왼쪽에 있는 수는 작거나 같다.
   중복되는 수를 포함한 배열은 현재 위치부터 탐색할 것이기 때문에 왼쪽에 있는 수는 탐색하지 않아도 된다.
   그래서 현재 위치에서부터 n까지 배열에 i번째 요소를 추가한다.
   

3. 중복 체크하기
   만들어진 배열이 중복되면 더이상 그 수열은 탐색하지 않는다. 중복되지 않을 경우 2번과정을 계속 수행한다.
   

4. m개 비내림차순 부분수열
   만들어진 배열의 길이가 m이면 출력하고 탐색을 멈춘다.
   

🥂코드

import sys; input = sys.stdin.readline
n, m = map(int,input().split())
arr = sorted(list(map(int,input().split())))
tmp = []
chk = set()

def isDuplicate(li):
    if li not in chk: 
        chk.add(li)
        return True
    return False

def dfs(inx):
    if len(tmp) == m:
        print(' '.join(map(str,tmp)))
        return
    for i in range(inx,n):
        tmp.append(arr[i])
        if isDuplicate(tuple(tmp)):
            dfs(i)
        tmp.pop()
dfs(0)