[BOJ] 15657 : N과 M (8) [백트랙킹](Python)

문제 링크

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

15657번: N과 M (8)

소스 코드

n,m = map(int,input().split())
nums = sorted(list(map(int,input().split())))

answers = []
def recipe(v):
    if len(v) == m: # m개를 다 뽑았으면 종료
        answers.append(v[:])
        return
    
    for idx in range(n):
        # 리스트 내 숫자보다 작은 경우는 패스
        if v and nums[idx] < v[-1]:
            continue
        else: # 리스트 내 숫자 이상인 경우 추가
            v.append(nums[idx])
        recipe(v) # 재귀
        v.pop() # 마지막 숫자 pop

recipe([]) # 공백 리스트로 시작

# 각 리스트의 모든 원소를 띄어쓰기로 구분하여 출력
for answer in answers: 
    print(*answer,sep=' ')

 

해설

• 백트랙킹, 재귀 함수

구조는 이전에 풀이한 'N과 M (8)' 문제와 거의 완벽하게 동일하기 때문에 링크를 남깁니다.

https://chanmuzi.tistory.com/178

[BOJ] 15654 : N과 M (5) [백트랙킹](Python)

 

재귀 함수의 로직에 대해 아주 간단히만 설명하면,

 

1) 입력으로 받는 리스트의 길이를 체크한다.

이때 길이가 문제에서 주어진 m, 즉 뽑아야하는 원소 개수와 동일한 경우 answers라는 정답 리스트에 해당 리스트를 추가한다.

리스트를 추가할 때는 복사해서 추가하도록 한다.

 

2) 리스트 v에 원소를 추가한다.

이때 조건문을 통해 리스트 내의 가장 마지막 원소 이상의 원소만 받을 수 있도록 한다.

문제 조건에 따르면 뒤에 나오는 숫자는 앞의 숫자 이상의 값이어야 하므로 이를 만족시킬 수 있는 조건문을 짠다.

만약 이 조건에 해당하지 않는 경우라면 continue를 통해 다른 원소를 추가하도록 한다.

 

3) 공백 리스트로 출발한다.

처음에는 어떤 숫자도 포함하지 않는 공백 리스트로 시작하여 원소를 하나씩 추가한다.

길이가 m이 되는 순간 return 하며 해당 리스트에서 원소를 하나씩 pop하고 다시 반복문을 돌게 된다.

 

위와 같이 요약할 수 있겠네요!

특히나 1)에서 왜 리스트를 복사하여 추가하는지에 대해서는 위에 올려둔 이전 게시물을 참고해주시면 되겠습니다 🙏🏻