[백준] 15666 N과 M (12)

문제

• N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하기.
  • N개의 자연수 중에서 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.
  • 고른 수열은 비내림차순이어야 한다.
• 1 <= M, N <= 8

 

풀이 1 (itertools 사용)

• 받은 수열을 set으로 중복 제거한 뒤 정렬하기
• 중복 허용한 조합 뽑아내기

 

from itertools import combinations_with_replacement

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

for seq in combinations_with_replacement(numbers, r=M) :
    print(*seq)

 

 

풀이 2 (generator 사용)

• itertools 사용하지 않는 경우 (직접 구현이 더 느리니까 itertools 사용하자)

def combinations_with_replacement(array, r) :
    for i in range(len(array)) :
        if r == 1 :
            yield [array[i]]
        else :
            for next in combinations_with_replacement(array[i:], r-1) :
                yield [array[i]] + next

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


for seq in combinations_with_replacement(numbers, r=M) :
    print(*seq)

 

풀이 3 (back tracking)

• dfs로 값을 하나씩 뽑아낸다.
  • for i in range(idx, N) 부분이 포인트~

_, M = map(int, input().split())
numbers = sorted(list(set(list(map(int, input().split())))))
N = len(numbers)
choose = [0 for _ in range(10)]

def dfs(idx, cnt) :
    global N, M
    if cnt == M :
        print(*[numbers[choose[idx]] for idx in range(cnt)])
        return
    
    for i in range(idx, N) :
        choose[cnt] = i
        dfs(i, cnt+1)

dfs(0, 0)

 

References

• 백준 backtracking 추천 문제