[Baekjoon] 15657 번 : N과 M (8) (Python, 백트래킹, 정렬)

[Baekjoon] 15657 번 : N과 M (8) (Python, 백트래킹, 정렬)

 

목차

 

 

 

 

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

15657번: N과 M (8)

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 92ms / 코드 길이 332B

 

본 문제는 N과 M 시리즈 - 백트래킹 문제다.
15649번 N과 M (1) : https://aigong.tistory.com/427
15650번 N과 M (2) : https://aigong.tistory.com/428
15651번 N과 M (3) : https://aigong.tistory.com/475
15652번 N과 M (4) : https://aigong.tistory.com/476
15654번 N과 M (5) : https://aigong.tistory.com/480
15655번 N과 M (6) : https://aigong.tistory.com/481
15656번 N과 M (7) : https://aigong.tistory.com/482
15657번 N과 M (8) : https://aigong.tistory.com/483
15663번 N과 M (9) : https://aigong.tistory.com/484
15664번 N과 M (10) : https://aigong.tistory.com/485
15665번 N과 M (11) : https://aigong.tistory.com/486
15666번 N과 M (12) : https://aigong.tistory.com/487

 

 

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

def dfs(idx):
    global n, m
    if idx == m:
        print(*s)
        return

    for i in l:
        if len(s) == 0 or s[-1] <= i:
            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)