[알고리즘/백트래킹] 15657번 : N과 M(8) - python

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

15657번: N과 M (8)

 

---

• 문제
• 소요시간: 5분 58초

 

---

• 설계하기(접근방법) 

1. 입력받기

n,m 을 입력받는다

 

2. 구현하기

 

비내림차순 순열을 구하기 위해서는

이전의 수열을 저장해주어 dfs의 인자로 넘겨주어야 한다

 

숫자가 너무 커지면 인덱스 넘버 자체를 넘겨

시간을 줄여주는 것이 좋겠지만

 

시간 초과가 넉넉하기 때문에

모든 숫자를 순회하되,

이전 숫자보다 크거나 같은 값만 lst에 추가해준다

 

 

3. 출력하기

ans를 출력한다

 

 

---

• 코드(출력)

n , m = map(int, input().split())
num_list = list(map(int, input().split()))
num_list.sort()

ans = []

def dfs(cnt, lst, before):
    if cnt == m:
        ans.append(lst)
    else:
        for i in num_list:
            if i >= before:
                dfs(cnt + 1, lst + [i], i)

dfs(0, [], num_list[0])

for i in ans:
    print(*i)

---

• 얻어갈 부분

1. 시간이 넉넉하지 않은 경우에는 index 넘버 자체를 넘겨서 시간을 줄여주도록 하자