[BOJ] 15665번: N과 M (11)

https://www.acmicpc.net/problem/15665

 

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

 

풀이

def go(arr):
    if len(arr) == M:
        print(' '.join(map(str, arr)))
        return
    for i in li:
        arr.append(i)
        go(arr)
        arr.pop()

N, M = map(int, input().split())
li = sorted(set(map(int, input().split())))
go([])

백트래킹을 사용하여 풀 수 있다.

수를 중복하여 사용할 수 있기 때문에 굳이 하나의 숫자가 여러 개 있을 필요가 없다. 따라서 set을 사용해 수가 중복되지 않도록 한 후 sort로 정렬했다.

 

go라는 함수로 백트래킹을 구현했는데, arr의 길이가 M일 경우 출력을 하고, 아닐 경우에는 반복문으로 하나씩 삽입한 후 다시 함수를 호출하여 출력하거나 또 삽입한다. 출력한 후에는 return과 pop을 하여 또다른 숫자를 삽입한다.