해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 15652번 N과 M(4) - 백트래킹

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다. 15651의 문제에서 약간 변형된 문제입니다.

https://zidarn87.tistory.com/329

2. 중복이 가능하기 때문에, 재귀 시 i를 넘겨주어 같은 수도 고를 수 있게 합니다.

3. 비내림차순이기 때문에 index 적용합니다. for 문은 index부터 시작하여, 비내림차순으로 출력하도록 합니다.

전체 코드

N, M = map(int, input().split())
lst = []

def dfs(cnt, index):
    if cnt - 1 == M:  # 탈출 조건
        print(' '.join(map(str, lst)))
        return

    for i in range(index, N+1):
        lst.append(i)
        dfs(cnt+1, i)
        lst.pop()
dfs(1, 1)