[백준 15652] N과 M (4) with Python

문제 링크

www.acmicpc.net/problem/15652

15652번: N과 M (4)

풀이

n, m = map(int, input().split())

def nm(n, m, seq=[]):
    if len(seq) == m:
        print(" ".join(seq))
    else:
        start = int(seq[-1]) if seq else 1
        for i in range(start, n+1):
            nm(n, m, seq+[str(i)])

nm(n, m)

재귀함수를 통해 seq[-1]부터 n까지의 수를 순회하면서(처음에는 seq이 비어있으므로 seq[-1] 대신 1) seq에 하나씩 추가하면서 seq의 길이가 m이 될 때마다 수열을 출력하도록 하였다.

 

즉, 처음에는 1부터 n까지 순회하면서 seq에 숫자를 추가하고 그 다음부터는 seq의 가장 마지막 원소와 같거나 큰 수를 n까지 계속 순회하면서 재귀호출을 반복하는 것이다.

 

이 문제는 itertools 모듈의 combinations_with_replacement 메소드를 활용하여 쉽게 해결할 수 있다.

itertools.combinations_with_replacement(iterable, r)은 iterable의 원소를 반복 사용하여 r개를 고르는 조합을 튜플로 반환한다. 즉, itertools.combinations에서 중복을 허용한 것과 동일하다.

import itertools

n, m = map(int, input().split())
lst = [str(x) for x in range(1, n+1)]
print("\n".join(map(" ".join, itertools.combinations_with_replacement(lst, m))))