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

 

문제 분석

• 1~n까지 자연수 중 m개 고른 수열
• 같은 수를 여러번 골라도 됨 (중복 허용)
• 고른 수열은 비내림차순이여야 한다. (비내림차순 : 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하는 경우)
• 즉 순서가 o
• 중복조합 (중복 o, 순서 x)

 

코드 설계

• 비내림차순을 어떻게 구현할 것인가

 

정답 코드

import sys
input = sys.stdin.readline

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

def dfs(start):
    if len(ans) == m:
        print(' '.join(map(str, ans)))
        return

    for i in range(start, n + 1):
        ans.append(i)
        dfs(i)
        ans.pop()
dfs(1)

 

itertools

from itertools import combinations_with_replacement
import sys
input = sys.stdin.readline

n,m = map(int, input().split())
arr = [i for i in range(1,n+1)]

for i in combinations_with_replacement(arr, m) : 
    for j in i : 
        print(j, end = ' ')
    print()