백준 15650번 파이썬 풀이

우선 재귀 함수의 사용법을 알아야 합니다.

이때, 매개변수를 업데이트하는 것이 중요한데,

이를 통해 재귀 호출시에 조건을 만족하는 새로운 매개변수 값을 전달할 수 있습니다.

이 문제에서는 다음과 같은 재귀 함수를 작성할 수 있습니다.

아래와 같은 구조를 숙지하셨다면 , 정답을 보시죠

def recursive_function(매개변수):
    if 종료조건:
        return

    # 재귀 호출
    recursive_function(매개변수 업데이트)

 

[정답코드]

def make_sequence(N, M, selected, start):
    # 수열이 M개가 되면 출력하고 종료
    if len(selected) == M:
        print(' '.join(map(str, selected)))
        return

    # start부터 N까지의 숫자 중에서 하나를 선택하여 수열에 추가하고, 재귀 호출
    for i in range(start, N+1):
        make_sequence(N, M, selected + [i], i+1)

# 입력 받기
N, M = map(int, input().split())

# 재귀 함수 호출
make_sequence(N, M, [], 1)

 

여기서는 매개변수로 선택된 수열과 시작 숫자를 함께 전달하도록 하였습니다. 

시작 숫자는 선택된 수열의 가장 마지막 숫자보다 큰 수부터 시작하게 됩니다.

make_sequence 함수를 정의합니다. 

이 함수는 N, M, selected, start 네 개의 매개변수를 받습니다.

 selected는 지금까지 선택된 수열을 저장하는 리스트입니다.

 

 start는 이전에 선택된 수 중 가장 마지막 수보다 큰 수부터 시작하도록 합니다.
종료 조건을 검사합니다. 

선택된 수열의 길이가 M과 같으면 선택된 수열을 출력하고 함수를 종료합니다.

for 루프를 이용하여 start부터 N까지의 숫자 중 하나를 선택하고, selected 리스트에 추가합니다.
make_sequence 함수를 재귀 호출합니다.

 이때, selected 리스트에 새로 선택된 수를 추가하고, start는 현재 선택한 수보다 1 큰 수를 시작으로 전달합니다.

모든 재귀 호출이 종료되면 함수를 빠져나와 선택된 수열을 출력합니다.
make_sequence 함수를 호출하며, 선택된 수열과 시작 숫자를 초기화합니다.
위 코드를 간단히 설명드리면, 

start 변수는 이전에 선택된 수 중에서 가장 마지막 수를 추적하기 위해 사용됩니다.

 이를 통해, 다음에 선택게 될 수를 start로 전달하여 중복된 수를 선택하지 않도록 합니다. 

또한, selected 리스트에 선택된 수를 추가할 때마다 

새로운 리스트를 생성하여 원본 리스트를 변경하지 않고 선택된 수열을 추적합니다.

마지막으로, 출력되는 수열은 join 메서드를 이용하여 공백으로 구분하여 출력하도록 하였습니다.

이와 같이 재귀 함수를 이용하여, 

중복 없이 오름차순으로 수열을 생성하는 문제를 해결할 수 있습니다.