-
[Python] 백준 15656 N과 M (7)알고리즘/문제풀이 2021. 12. 12. 12:43728x90
1. 문제 링크
https://www.acmicpc.net/problem/15656
2. 문제 요약
- N개의 자연수 중 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
3. 아이디어 정리
- 증가하는 순서 출력이므로 정렬을 진행한다.
- 백트래킹으로 M개를 선택할 때 출력하게 한다. ⇒ 종료 조건
- 같은 수 여러 개 가능하기 때문에 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. 결론
- 백트래킹 문제
'알고리즘 > 문제풀이' 카테고리의 다른 글
[Python] programmers 여행 경로 (0) 2021.12.12 [Python] 백준 2580 스도쿠 (0) 2021.12.12 [Python] programmers 뉴스 클러스터링 (0) 2021.12.04 [Python] programmers 입국심사 (0) 2021.12.04 [Python] programmers 교점에 별 만들기 (0) 2021.11.27