[백준] 15657 N과 M(8) - 파이썬 DFS 재귀

문제집 출처 :: 백준 N과 M https://www.acmicpc.net/workbook/view/2052

 

이전글

2020/03/02 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15649. N과 M (1) 파이썬

2020/03/02 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15650 N과 M(2) 파이썬

2020/03/03 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15651-15652. N과 M(3)-(4) 파이썬

2020/03/08 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15654 N과 M(5) 파이썬

2020/03/08 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15655 N과 M(6) 파이썬

2020/03/14 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15656 N과 M(7) - 파이썬 DFS 재귀

---

문제출처 https://www.acmicpc.net/problem/15657

[백준] 15657 N과 M(8) - 파이썬 DFS 재귀

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

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

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력	예제 출력
3 1  4 5 2	2 4 5
4 2 9 8 7 1	1 1 1 7 1 8 1 9 7 7 7 8 7 9 8 8 8 9 9 9

 

입력 [1,7,8,9] 중 2개 뽑음, 같은걸 다시 뽑을 수 있음 순서가 의미 없음, 출력 [1,7] == [7,1] 같아서 하나만 [1,7] 출력

[7,7] = [7,7] 도 같은 것이 됨

 

---

<8번 풀이 PASS>

 
# # 8번. [백준] 15657
# #  n 갯수들 중에 m 개 뽑기. 중복사용가능. 순서없음. [1,2]=[2,1] 같게 봄
n,m = map(int,input().split())
numbers = list(map(int,input().split())) # 1~n까지
numbers.sort()
is_number = [0 for _ in range(m)] # 출력 개수
#check = [False for _ in range(n)] # 사용여부 필요없음
def dfs(idx,next):
    if idx >= m: # 0부터 m출력개수 되면
        print(*is_number)
        return
    for i in range(next,n):
        is_number[idx] = numbers[i]
        dfs(idx+1,i) # 나 다음부터~
dfs(0,0)
 
 
 

재귀로 들어갔을 때, 또 골랐던 것을 고를 수 있으므로

다시 처음부터 or 나(i) 다음부터 탐색하면 안되고

나부터 다시 해줘야 해서 next 에 i 로 해준다

 

 

<지난 7번 풀이 참고>

 

 
# # 7번. [백준] 15656
# #  n 갯수들 중에 m 개 뽑기. 중복사용가능. 순서있음. [1,2],[2,1] 다르게 봄
n,m = map(int,input().split())
numbers = list(map(int,input().split())) # 1~n까지
numbers.sort()
is_number = [0 for _ in range(m)] # 출력 개수
#check = [False for _ in range(n)] # 사용여부 필요없음
def dfs(idx,next):
    if idx >= m: # 0부터 m출력개수 되면
        print(*is_number)
        return
    for i in range(next,n):
        is_number[idx] = numbers[i]
        dfs(idx+1,next)
dfs(0,0)
 
 

재귀로 들어갔을 때, 다시 처음부터 탐색하기 때문에 next = 0 이므로 없어도 됨.