[백준 15652][python] N과 M (4)

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
  (링크 - https://www.acmicpc.net/problem/15652)

해결

백트래킹(dfs)을 이용해 해결
1. 결과값을 담는 arr 배열을 생성한다
2. k는 배열에 있는 값의 길이다
3. k와 m이 같아지면 arr을 프린트한다
4. last변수를 이용해 이전에 방문한 숫자를 저장하고, 해당 숫자보다 같거나 큰 값을 배열의 다음 위치에 넣도록 한다.
5. k 값을 늘리고 함수를 재호출 한다.

코드

n, m = map(int, input().split())

arr = [0]*m

def dfs(arr, k, last): #k == 리스트에 들어있는 수의 개수
    if k == m:
        for ar in arr:
            print(ar, end = ' ')
        print("")
        return 
    
    for i in range(1, n+1):
        if last <= i:
            arr[k] = i
            dfs(arr, k+1, arr[k])

dfs(arr, 0, 1)

기존 백트래킹 템플릿을 보고 짜려고 하니 헷갈렸다. last 변수를 추가해 간단히 해결!