[Python] 백준 15656 N과 M (7)

1. 문제 링크

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

15656번: N과 M (7)

2. 문제 요약

• N개의 자연수 중 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

3. 아이디어 정리

1. 증가하는 순서 출력이므로 정렬을 진행한다.
2. 백트래킹으로 M개를 선택할 때 출력하게 한다. ⇒ 종료 조건
3. 같은 수 여러 개 가능하기 때문에 for 문에 조건을 없이 넣는다.

 

4. 문제 풀이

4-1. 내 풀이

import sys

def dfs(list_):
    if len(list_) == m:   # 1. Base condition(종료 조건)
        print(*list_)
        return

    for i in arr:         # 2. 백트래킹 
        list_.append(i)
        dfs(list_)
        list_.pop()

n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()

dfs(list())

 

 

5. 결론

• 백트래킹 문제