PS

[BOJ] 15666번 N과 M (12) 문제 - Python

식용감자 2021. 3. 4. 14:12

www.acmicpc.net/problem/15666

 

15666번: N과 M (12)

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

www.acmicpc.net

 

중복은 가능하나 비오름차순으로 출력해야한다.

 

따라서 입력받은 숫자를 set 으로 변환 후 다시 list 로 변환해서 겹치는 것을 제거해주고 sort 한뒤 뽑기만 하면 된다.

 

element 안에 아무것도 없을 때는 그냥 순서대로 집어넣고 원소가 있을 때만 비오름차순으로 뽑아준다.

 

 


N, M = map(int, input().split())
numbers = list(map(int, input().split()))
numbers = list(set(numbers))
numbers.sort()

element = []
def dfs(depth):

    if depth == M:
        print(*element)
        return

    for i in range(len(numbers)):
        if not element:
            element.append(numbers[i])
            dfs(depth + 1)
            element.pop()
        else:
            if element[-1] <= numbers[i]:
                element.append(numbers[i])
                dfs(depth + 1)
                element.pop()

dfs(0)