[Python][백준/BOJ] 15655번 : N과 M (6)

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

15655번: N과 M (6)

 

내 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
num = list(map(int, input().split()))
num.sort()
tmp = []
visited =[False for _ in range(1000001)]
def dfs(start):
    if len(tmp) == m:
        print(' '.join(map(str, tmp)))
        return
    
    for i in range(n):
        if not visited[i] and start < num[i]:
            tmp.append(num[i])
            visited[i] = True
            dfs(num[i])
            tmp.pop()
            visited[i] = False
            
dfs(0)

 

dfs, 입력받은 수를 중복 없이 오름차순 정렬하기

중복 없이 출력해야 하므로 visited라는 배열을 이용하여, 방문을 했는지를 검사했다.

num =[] 이라는 리스트에 입력받은 수를 넣어주었다.

그리고 start 라는 변수를 사용해서, 계속 start에 num[i] 를 넣어주었다.

주의할 점은 start를 num 리스트의 최솟값으로 하기 위해 dfs(min(num)) 으로 했다가 틀렸는데,

조건문에 start < num[i]일 때는 for문에 해당되지 않도록 했기 때문에 num의 최솟값이 수열에 포함되지 않게 된다.

그래서 문제에 있는 자연수라는 조건을 활용하여 dfs(0)를 넣어주었다.

성공!