백준 15663 N과 M (9)

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

 

 이 문제는 N과 M이 주어지고 N개의 자연수 중 M개를 고른 수열을 중복없이 사전순으로 출력하는 문제이다. 이 문제에서 주어지는 N개의 자연수는 중복될 수 있으므로, 필자는 그냥 고를 수 있는 모든 경우의 수열을 구하고 집합 자료형과 sorted() 함수를 이용하여 간단하게 구했다. 처음엔 시간초과가 나오지 않을까 했지만 N이 8 이하로 많이 해봤자 수열이 8! 밖에 나오지 않는지라, 그렇게 구하였다.

 

def DFS(seq,visited):
    if len(seq) == M:
        ans_set.add(tuple(seq))
        return
    
    for i in range(len(Ns)):
        if not visited[i]:
            visited[i] = True
            DFS(seq+[Ns[i]],visited)
            visited[i] = False



N,M = map(int,input().split())
Ns = list(map(int,input().split()))

ans_set = set()

DFS([],[False for _ in range(N)])

for i in sorted(list(ans_set)):
    print(' '.join(str(a) for a in i))