[Baekjoon] 15654 번 : N과 M (5) (Python, 백트래킹, 정렬)
[Baekjoon] 15654 번 : N과 M (5) (Python, 백트래킹, 정렬)
https://www.acmicpc.net/problem/15654
15654번: N과 M (5)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열
www.acmicpc.net
코드 링크
https://github.com/stellaluminary/Baekjoon
GitHub - stellaluminary/Baekjoon
Contribute to stellaluminary/Baekjoon development by creating an account on GitHub.
github.com
Python
방법 1 - 메모리 30840KB / 시간 244ms / 코드 길이 317B
본 문제는 N과 M 시리즈 - 백트래킹 문제다.
N과 M (1) : https://aigong.tistory.com/427
N과 M (2) : https://aigong.tistory.com/428
N과 M (3) : https://aigong.tistory.com/475
N과 M (4) : https://aigong.tistory.com/476
N과 M (5) : https://aigong.tistory.com/480
N과 M (6) : https://aigong.tistory.com/481
N과 M (7) : https://aigong.tistory.com/482
N과 M (8) : https://aigong.tistory.com/483
N과 M (9) : https://aigong.tistory.com/484
N과 M (10) : https://aigong.tistory.com/485
N과 M (11) : https://aigong.tistory.com/486
N과 M (12) : https://aigong.tistory.com/487
사전 순으로 증가하는 순서는 초기 입력받는 list를 정렬하고 백트래킹하면 된다.
def dfs(idx):
global n, m
if idx == m:
print(*s)
return
for i in l:
if i not in s:
s.append(i)
dfs(idx+1)
s.pop()
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
s = []
dfs(0)
