[백준] 15654 N과 M (5)

문제

• N개의 자연수와 자연수 M이 주어졌을 때, N개 중 M개 고른 모든 수열 구하기
  • 1 <= M <= N <= 8
• 순서가 다르면 다른 수열
• 수열은 사전 순 오름차순으로 출력하기

 

풀이 1

• permutation 라이브러리 이용
• 전체 수열을 오름차순으로 정렬한 뒤 M개 뽑은 수열 출력하기

 

from itertools import permutations

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

for perm in permutations(numbers, M):
    print(*perm)

 

풀이 2

• 재귀 이용해 풀이
  • depth : 현재 뽑은 숫자의 개수
  • n : 현재 남은 숫자의 개수

1. 숫자를 1개 뽑아서 정답 배열에 추가
2. 해당 숫자를 수열에서 제외하고 다시 함수 호출
3. 뽑았던 숫자 다시 제거 

import sys
sys.setrecursionlimit(10**4)

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

answer = []
def solve(depth, numbers, n):
    if depth == M :     # M개 뽑은 경우
        print(*answer)
    
    for i in range(n):	# 1개씩 순서대로 숫자 추가하기
        answer.append(numbers[i])
        solve(depth+1, numbers[:i]+numbers[i+1:], n-1)
        answer.pop()

solve(0, numbers, N)

 

References

• 백준 15654번
• 2023.05.03 오늘의 문제