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

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

15666번: N과 M (12)

 

---

• 문제
• 소요시간: 11분 53초

---

• 설계하기(접근방법) 

1. 입력받기

n,m 과 수열을 입력받는다

 

2. 구현하기

같은 숫자를 여러번 골라도 되니

set을 통해서 리스트의 중복 원소를 없애준다

그 후 list를 sort() 해주어 수열이 순차적으로

출력되도록 조정해준다

 

그 다음 dfs 백트래킹을 통해서

수열을 더해나가는데

문제의 조건인 비내림차순 수열이어야 하기 때문에

 

이전 원소보다 크도록 다음 원소를 정해준다

before = i 로 저장한 후

i 의 값을 dfs의 인자로 함께 넘겨주어 구현한다

 

3. 출력하기

ans를 출력한다

---

• 코드(출력)

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

ans = []

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

dfs(0, [], 0)

for i in ans:
    print(*i)

---

• 얻어갈 부분

1. 이전 값을 dfs의 인자로 넘겨서 다음 원소의 크기를 조절해줄 수 있었다,