[Python] 백준 온라인 저지 N과 M 시리즈(6) - 15655번

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

15655번: N과 M (6)

 

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

 

 

 

[Python]

 

풀이 방법:

 

중복 허용하지 않고,

다음 깊이 탐색 후, 탐색 이후의 범위에서 반복문을 돌려주면 된다.

n과 m 시리즈 2 15650번과 로직이 비슷하다.

for i in range(n): 
        if visited[i] == 0: 
            
            ##### code ######
            
            # 순열 부분과의 차이점 
            for j in range(i+1, n): 
                visited[j] = 0

 

 

 

코드:

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
visited = [0 for _ in range(n)]
lists = list(map(int, input().split()))
lists.sort()
out =[] # 결과

def dfs(cnt): # dfs 이용
    if cnt == m:
        print(' '.join(map(str, out)))
        return
    
    for i in range(n):
        if visited[i] == 0:
            visited[i] = 1 # 방문 처리
            out.append(lists[i])
            
            solve(cnt+1) # 다음 깊이 탐색
            out.pop() # 탐사 내용 제거
            
            for j in range(i+1, n):
                visited[j] = 0
                
dfs(0)