[BOJ][Python] 15650 N과 M(2)

[문제 및 출처]

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

15650번: N과 M (2)

[어떻게 풀까?]

문제의 조건은 다음과 같다.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

고른 수열은 오름차순이어야 한다.

아! 그렇다면 내가 진행하고 있는 수보다 큰 수를 다음에 진행하면 되지 않을까?

이런식으로 말이다.

 

[코드]

N, M = map(int, input().split())

used = [False] * (N+1)
answer = []

def dfs(before, N, M):
    #조건에 충족하면 출력
    if len(answer) == M: 
        print(" ".join(map(str, answer)))
        return

    for i in range(before, N+1):
        if not used[i]: 
            used[i] = True
            answer.append(i)

            dfs(i+1, N, M)
            
            #다시초기화
            used[i] = False 
            answer.pop()

dfs(1, N, M)

[코드설명]

before이라는 변수를 만들어 주었다. 이 변수의 기능은 그 전에 진행했던 수를 체크해 주는 기능이다.

그 수보다 큰 수 부터 세주게 되면은 자연스레 오름차순이 되지 않을까?