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

 

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

15652번: N과 M (4)

 

 

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

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

 

N과 M(2)와 N과 M(3) 문제의 조건을 합쳤다.

 

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

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

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

 

start는 오름차순으로 배열을 만들기 위해 정해준다.

그러나 여기서는 비오름차순이기 때문에 자기 자신을 포함한다.

그러므로 재귀호출을 할 때, 1씩 증가하지 않아야한다.

 

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, n, m)
        arr.pop()

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

go(0, 0, n, m)