[백준/브루트포스] 15650 N과 M (2) (Python, 파이썬)

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

15650번: N과 M (2)

 

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

15650번 N과 M (1)에서 추가된 조건은 두 번째 조건이다.

 

재귀함수를 이용하여 풀었는데, 이 때 재귀함수는 어떤 위치에 올 수 있는 수를 결정하는 용도이다.

재귀함수에서 중요한 것은 종료조건이다.

여기서의 종료조건은 M개를 다 뽑았을 때이다. 그때 배열에 저장한 수를 모두 출력하면 된다.  

 

오름차순으로 구하기 위해 start를 추가했다. 

start는 재귀로 호출 될 때마다 1씩 증가한다.  

start 보다 큰 수 만을 탐색하여 arr 배열에 담는다면, 그 배열의 요소들은 오름차순으로 저장 될 것이다.

 

start를 추가한 코드는 다음과 같다.

import sys
input = sys.stdin.readline

def go(index, start, n, m):
    if index == m:
        print(' '.join(map(str, arr)))
        return

    for i in range(start, n):
        if visited[i]:
            continue

        visited[i] = True
        arr.append(i+1)

        go(index+1, i+1, n, m)

        visited[i] = False
        arr.pop()

n, m = map(int, input().split())
visited = [False] * 10
arr = []

go(0, 0, n, m)

 

그러나 start보다 작은 수를 탐색하지 않겠다고 하면, visited 배열의 존재는 필요없어진다.

이미 탐색한 것은 다시 탐색하지 못하게 start를 만들었기 때문이다.

 

그렇기 때문에 다음과 같이 작성 할 수 있다. 

import sys
input = sys.stdin.readline

def go(index, start, n, m):
    if index == m:
        print(' '.join(map(str, arr)))
        return

    for i in range(start, n):
        arr.append(i+1)

        go(index+1, i+1, n, m)
        arr.pop()

n, m = map(int, input().split())
arr = []

go(0, 0, n, m)