💻 백준 15652: N과 M(4)

문제 소개 🧐

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

  • 1부터 N까지 자연수 중에서 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.
  • 고른 수열은 비내림차순이어야 한다.

입력 📝

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

출력 📤

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

제한 ❌

  • 시간 제한: 1 초
  • 메모리 제한: 512 MB

첫 번째 시도: itertools.combinations_with_replacement ✅

Idea

파이썬의 itertools 라이브러리에 있는 combinations_with_replacement 함수를 사용하면 중복을 허용하는 조합을 쉽게 얻을 수 있다. 이 함수는 결과를 비내림차순으로 반환하기 때문에, 문제에서 요구하는 조건과 정확히 일치한다.

Code

import sys
from itertools import combinations_with_replacement

n, m = map(int, sys.stdin.readline().split())

li = combinations_with_replacement(range(1, n+1), m)
for num in li:
    print(*num)

Result

  • 성공! itertools 라이브러리 덕분에 별도의 백트래킹 구현 없이 간결하게 문제를 해결할 수 있었다.

개선할 부분 🤔

  • 만약 itertools를 사용하지 않고 직접 구현해야 한다면, 백트래킹(Backtracking) 알고리즘을 사용하여 재귀적으로 중복 조합을 생성하는 방법을 고려해볼 수 있을 것 같다.