[백준] 15657 - N과M

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

15657번: N과 M (8)

문제 한줄 이해

-주어진 N개의 숫자 중에서 M개를 뽑을때 이미 선택된 숫자를 뽑아되는 경우에서 겹치지 않는 수열 구하기

 

생각난 풀이

1번째 방법: 이전 N과 M의 문제와 아이디어는 같지만 추가된 조건이 있다. 1부터 N까지 숫자가 아닌 주어진 N개의 숫자 중에서 M개를 뽑아야 하는점, 비내림차순으로 출력해야하는 점

백트래킹이 생각나 재귀를 통한 DFS를 사용했다.

일단 기본적인 아이디어는 https://9-bin.tistory.com/entry/%EB%B0%B1%EC%A4%80-15652-N%EA%B3%BC-M 에 있다!

주어진 N개를 다루기 위해서 나는 리스트로 입력을 받았고 비내림차 순으로 출력해주기 위해 재귀함수를 실행하기 전에 sort를 사용해 정렬을 해주었다.

이유는 정렬을 해주게 되면 for문에 의해 순차적으로 탐색을 진행할 것이기 때문이다.

import sys

n, m= map(int,sys.stdin.readline().split())
numlist = list(map(int,sys.stdin.readline().split()))
numlist.sort()

result = []

def back(start):
    if len(result) == m:
        print(*result)
        return
    
    for i in range(start,n):
        if numlist[i] not in result:
            result.append(numlist[i])
            back(0)
            result.pop()
back(0)