[BOJ 백준] - N과M (2) 15650 Python

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

• n과 m을 입력받는다.
• 1부터 n까지의 수로 만들 수 있는 길이가 m인 수열을 모두 출력한다.
• 단, 수열은 오름차순이어야 한다.

재귀를 이용해서 풀었다.

• 배열 nums 는 길이 m인 수열을 저장하는 역할을 한다.
  m개 숫자를 저장해야 하기 때문에 m으로 초기화했다.
• nums의 0번째 값은 수열을 첫번째 값이 된다.
  nums에는 0번째부터 m-1번째까지 증가하는 형태로 저장되면 된다.
• 재귀호출은 종료조건이 중요하다 종료조건을 보자.
  • l이 m이면 종료된다.
  • l은 재귀호출의 깊이이자 nums의 인덱스가 된다.
    nums 배열을 모두 채웠다면 증가하는 한 개 수열을 완성한 것이므로 nums의 수를 차례대로 출력하고 재귀호출을 종료한다.

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

def solve(nums, l):
    if l == m:
        for num in nums:
            print(num, end=' ')
        print()
        return
    for i in range(1, n+1):
    # l이 0보다 큰 경우는 수열의 첫번째 값이 아니라는 의미
    # 수열의 첫번째가 아니라면 이전값보다 큰 지 비교해야 한다.
        if l > 0:
            if i > nums[l-1]: 
                nums[l] = i
                solve(nums, l+1)
    # l이 0인 경우 수열의 첫번째 값이므로 무조건 값을 넣는다.                 
        else:
            nums[l] = i
            solve(nums, l + 1)

nums = [0] * m
solve(nums, 0)

문제를 다 풀고 알고리즘 분류를 보니 백트래킹이다..
한 번만에 슥 풀리고 정답을 받아서 고치기 싫다. ㅎ