[백준] 15655 N과 M (6)

문제

• N개의 자연수와 자연수 M이 주어졌을 때, 조건을 만족하는 길이가 M인 수열 모두 구하기
  • 1 <= M <= N <= 8
• N개 자연수 중 M개를 고른 오름차순 수열
• 조건을 만족하는 수열을 오름차순으로 출력하기

 

풀이 1

• 조합 - 라이브러리 이용
• N개 자연수 오름차순으로 정렬하고, 조합 구한 뒤 출력

from itertools import combinations

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

for comb in combinations(numbers, M):
    print(*comb)

 

 

풀이 2

• 재귀 이용하기
• N개 자연수를 오름차순으로 정렬
• 각 숫자를 돌아가면서 뽑되, 중복을 허용하지 않으므로 자신 이후의 숫자만 뽑기 후보로 넣음

 

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

comb = []
def solve(depth, numbers):
    if depth == 0 :
        print(*comb)
        return

    for i in range(len(numbers)):
        comb.append(numbers[i])
        solve(depth-1, numbers[i+1:])
        comb.pop()

solve(M, numbers)

 

References

• 백준 15655
• 2023.05.02 오늘의 문제