[B]BOJ1182 - 재귀, itertools.combination으로 풀어보기

코드는 github repository 참고

상단이 recursive

하단이 itertools.combination으로 푼 코드이다.

recursive로 푸니까 공간, 시간적으로 더 효율적이었다.

상단의 경우 재귀 함수를 호출하며 stack 메모리를 소비한다.

하단은 모든 경우의 수, 부분 수열 조합을 combination 모듈을 사용하여

리스트 형태로 메모리에 적재한 후에 

리스트를 훑으면서 검사하는 알고리즘이다.

1182 문제의 조건과 제약사항에서는

두 방식을 사용해도 충분했다.

재귀 방식에 대한 보충 설명

def search (lev):
	global N, S, arr, choose, ans

	# print("current lvl : ", lev)
	# print("current choose : ", choose)
	# print()

	# base case
	if lev == N:
		if choose and sum(choose) == S:
			ans+=1
		return

	# select elements whose index is lev
	choose.append(arr[lev])
	# print("choosing")
	search(lev+1)
	choose.pop()


	# not choosing element whose index is lev (select next instead)
	# print("not choosing")
	search(lev + 1)


N, S = map(int, input().split())
arr = list(map(int, input().split()))
choose = []
ans = 0

search(0) # recursive method

print(ans)

재귀 호출 시 함수에 전달되는 level 인자는 0부터 시작한다.
문제에서는 양의 길이의 부분 수열의 합을 검사하지만
코드에서 합을 계산하는 전제 조건에는 lev==N이 있다.
여기서 N은 입력된 배열의 크기로
base case로서 항상 lev==N 조건을 검사하게 된다.

주석을 참고하면,
lev 값으로 하여금 선택된 개수 + 선택 안 한 개수 = N인지 항상 검사한다.


아래 그림을 참고 


입력된 배열의 원소를 선택함/선택 안 함의 경우의 수를 따져야 하기 때문에
level==N 조건이 필요하다.

그림에서 오른쪽 Array가 입력받은 배열이고,
가운데 테이블이
선택함(O)
선택 안 함(X)
을 체크한 표이다.
여기서 O의 개수와 X의 개수는 항상 N(=5)로 유지됨을 알 수 있다.

재귀 과정에서 
lvl이 N에 도달했을 때에 sum 계산을 수행한다.

도달하지 않았다면 lvl에 도달하기 위해
lvl+1을 해주는데

선택했을 때는
choose 배열에 append를 한 후, lvl+1 인자를 재귀 함수에 건네서 호출하고

선택을 안 했을 때는
choose 배열 append를 하지 않고 lvl+1 인자를 재귀 함수에 건네서 호출한다.

선택한 경우의 재귀함수 호출이 끝난 뒤에는
choose.pop()을 통해
전 단계에서 삽입된 원소를 제거해준다.


재귀함수이지만 지역변수가 아닌 Global 변수
global arr, choose를 선언해준 덕분에 위와 같은 접근이 가능하다.
그렇지 않다면 호출 할 때마다 인자로 배열들의 주소를 전달해주어야 했을 것이다.



정리
- choose를 해도 choose를 하지 않아도 lvl은 올라간다.
- lvl은 N값에 도달해야만 sum()계산을 수행한다.
  모든 배열 원소들에 대해 쓸 지 말 지를 결정해야하기 때문이다.