[15650] N과 M (2)

 

백준 Silver III | 15650 | Python | 문제 링크

문제 설명

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

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

입력

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

출력

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

입출력 예

입력	출력
4 2	1 2 1 3 1 4 2 3 2 4 3 4

 

나의 풀이

풀이 1

def backtrack(start, seq):
    if len(seq) == m:
        print(' '.join(map(str, seq)))
        return
    for i in range(start, n + 1):
        seq.append(i)
        backtrack(i + 1, seq)
        seq.pop()

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

풀이 설명

오름차순 조건 때문에 15649와 달리 visited 배열이 필요 없다. 다음 재귀 호출의 시작점을 i + 1로 넘기는 것만으로 중복 제거와 오름차순을 동시에 보장한다.

• start — 현재 수열에 추가할 수 있는 최솟값. 항상 이전에 추가한 수보다 크므로 오름차순이 보장된다.
• backtrack(i + 1, seq) — 같은 수를 두 번 쓰지 않도록 다음 후보를 i + 1부터 시작

풀이 2

from itertools import combinations

n, m = map(int, input().split())
for c in combinations(range(1, n + 1), m):
    print(' '.join(map(str, c)))

itertools.combinations는 입력 순서를 유지하면서 오름차순 조합을 생성한다. 15649의 permutations를 combinations로 바꾸는 것만으로 오름차순 조건이 충족된다.