반응형
15654
https://www.acmicpc.net/problem/15654
15654번: N과 M (5)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열
www.acmicpc.net
[정답]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import sys
N, M = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))
num.sort()
visited = [False]*N
result = []
def dfs(depth):
if depth == M:
print(' '.join(map(str, result)))
for i in range(N):
if not visited[i]:
result.append(num[i])
visited[i] = True
dfs(depth+1)
result.pop()
visited[i] = False
dfs(0)
|
cs |
.
.
.
[풀이]
dfs를 이용하는 문제.
수열을 먼저 오름차순으로 정리.
탐색했는지 기록하는 리스트 visited, 출력할 결과를 저장하는 리스트 result를 만들어주고
재귀문을 이용한 dfs탐색을 한다.
dfs에 관한 기초적인 문제.
p.s.
까먹고 있어 잠시 해맸다.
반응형
'백준 문제풀이' 카테고리의 다른 글
| [백준 10815] 파이썬 : 숫자 카드 (0) | 2021.10.10 |
|---|---|
| [백준 18310] 파이썬 : 안테나 (0) | 2021.10.09 |
| [백준 5555] 파이썬 : 반지 (0) | 2021.10.08 |
| [백준 11652] 파이썬 : 카드 (2) | 2021.10.08 |
| [백준 1049] 파이썬 : 기타줄 (0) | 2021.10.07 |