[실버 3] 15652번: N과 M (4)

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

15652번: N과 M (4)

---

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

사고의 흐름

• N과 M (2) 문제에서 bool 타입 List의 원소를 i번째까지만 바꾸면 끝이지 않을까? 

내가 작성한 소스코드

import sys
r = sys.stdin.readline


def print_seq(n, m, seq, is_used, depth):
    if depth == m:
        for v in seq:
            print(v, end=" ")
        print()
        return

    for i in range(1, n+1):
        if is_used[i] == False:
            seq.append(i)
            for j in range(1, i):
                is_used[j] = True
                
            print_seq(n, m, seq, is_used, depth+1)
            
            seq.pop()
            for j in range(1, i):
                is_used[j] = False


n, m = map(int, r().split())
is_used = [False] * (n+1)
print_seq(n, m, [], is_used, 0)

남이 작성한 소스코드

bomul1128 님:
https://www.acmicpc.net/source/39494267

피드백

• extend() 함수나 + 연산자를 사용해서 List와 List를 합칠 수 있다. 그러므로 재귀 함수의 매개변수에 seq + [i] 를 넘겨주면 따로 Append할 필요가 없어진다.