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

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

 

목차

 

 

 

 

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

15664번: N과 M (10)

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

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

 

본 문제는 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

 

 

15663번의 연장으로 다음 조건을 만족하도록 조건문을 수정한다.

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

 

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

    overlap = 0
    for i in range(n):
        if not visit[i] and overlap != l[i] and (len(s) == 0 or s[-1] <= l[i]):
            visit[i] = 1
            s.append(l[i])
            overlap = l[i]
            dfs(idx+1)
            visit[i] = 0
            s.pop()

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
l = sorted(list(map(int, input().split())))
visit = [0]*n
s = []
dfs(0)