[백준 파이썬] 15654 N과 M(5)

[백준 파이썬] 15654N과 M(5) 

문제

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

N개의 자연수는 모두 다른 수이다.

-N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이주언지다

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10000보다 작거나 같은 자연수이다.

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

풀이

이 문제는 백트래킹을 이용한 문제로 백트래킹 알고리즘은 모든 경우의 수를 탐색하면서 현재 주어진 조건과 맞는 것을 선택하고 아닐 경우 되돌아가는 재귀적 탐색을 수행하는 알고리즘이다 

def nm(a,m,data,array):
    if a==m:
        return print(*data)
    else:
        for i in range(len(array)):
            if array[i] not in data:
                data.append(array[i])
                nm(a+1,m,data)
                data.pop()

나는 조건에 맞게 돌아가는 재귀 함수를 만들었다.

함수의 변수 a는 현재 선택된 수가 몇 개인지 의미하고 m은 최대 몇 개까지 뽑아야 하는 수, date, 뽑는 수열을 저장할 배열, array는 주어진 배열을 의미한다.

 

a가 m이 아니면 array를 for문을 돈다 만약 현재 선택된 값이 data에 없다면 추가하고 다시 함수를 반복하는 재귀를 하면 재귀하는 함수가 끝이 나면 pop를 이용해서 현재 추가한 값을 빼서 다음 경우의 수를 탐색한다.

 

코드

def nm(a,m,data,array):
    if a==m:
        return print(*data)
    else:
        for i in range(len(array)):
            if array[i] not in data:
                data.append(array[i])
                nm(a+1,m,data)
                data.pop()



n,m=map(int,input().split())

array=list(map(int,input().split()))

array.sort()



nm(0,m,[],array)

결과