[Python/코테] 백준 15656 N과 M(7)

15656 N과 M(7)

문제 및 조건 설명: https://www.acmicpc.net/problem/15656

알고리즘 설계

모든 수열을 구해야 하고, N과 M의 범위가 크지 않으므로 모든 경우를 탐색하는 백트래킹을 활용한다.

백트래킹은 DFS로 전체를 탐색하되 조건이 맞지 않으면 중단하는 알고리즘이다.

 

알고리즘 구현

출처: https://honggom.tistory.com/109

import sys

n, m = map(int, input().split())
arr = list(map(int, sys.stdin.readline().split()))
sub = []


def func():
    # m개 완성 되었으면 종료
    if len(sub) == m:
        print(*sub)
        return

    for k in range(n):
        # 하나 추가하고
        sub.append(arr[k])
        # 나머지 정하기
        func()
        # 현재 원소로 가능한 경우는 윗줄에서 끝남
        # 다음 원소 추가를 위해 pop
        sub.pop()

arr.sort()
func()

나다어

• sub.pop()을 하지 않아서 무한 루프에 빠졌었음. 재귀적인 관점에서 생각하려면, 크게 생각해야 한다. 함수 한 번의 동작이 아닌 함수의 "역할"로 이해해보자.
  정답 코드에서 func()의 역할은 추가한 뒤 다음 단계로 이동하는 것이다. sub.pop()이 실행되기 전에 func()에서는 base condition까지 도달하며 모든 경우의 수를 탐색한 뒤 종료될 것.