[백준] 15656 N과 M (7)

문제

• N개의 자연수와 자연수 M이 주어졌을 때, 조건을 만족하는 길이가 M인 수열 모두 구하기
  
  • 1 <= M <= N <= 7
• N개의 자연수 중에서 중복을 허용해 M개 고르기
• 조건을 만족하는 수열을 오름차순으로 한 줄에 하나씩 출력하기

 

풀이 1

• 파이썬 라이브러리를 이용한 풀이
• product 이용해 가능한 모든 수열 찾기

from itertools import product

N, M = map(int, input().split())
numbers = list(map(int, input().split()))
numbers.sort()

for comb in product(numbers, repeat=M):
    print(*comb)

 

풀이 2

• 재귀 이용한 풀이

N, M = map(int, input().split())
numbers = list(map(int, input().split()))
numbers.sort()
combs = []	# 수열 저장 변수

def solve(depth, N, M):
	# 모든 숫자를 뽑은 경우
    if depth == M : 
        print(*combs)
        return
    # 숫자 하나씩 돌아가면서 선택하기
    for i in range(N):
        combs.append(numbers[i])
        solve(depth+1, N, M)
        combs.pop()

solve(0, N, M)

 

References

• 백준 15656
• 2023.05.02 오늘의 문제