본문 바로가기
알고리즘/백트래킹

[백준][Python] 1182번 부분수열의 합

by 임짠짠 2022. 8. 3.
반응형
 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

 

 

코드

n, s = map(int,input().split())
n_list = list(map(int,input().split()))

cnt = 0

def dfs(num,sum):
	global cnt
	if num >= n:
		return
	sum += n_list[num]
	if sum == s:
		cnt += 1


	dfs(num+1,sum)
	dfs(num+1,sum-n_list[num])

dfs(0,0)
print(cnt)

 

설명

dfs를 이용해 재귀로 문제를 풀었다.

해당 원소를 포함하는 경우와 포함하지 않는 경우로 나눠서 인덱스를 늘려갔다.

해당 원소를 포함하지 않는 경우에는 sum 값을 넘겨줄 때 해당 원소가 가리키는 값을 빼주고 넘겨줬다.

 

처음에 global cnt를 정의해주지 않고 코드를 돌려보니

 local variable 'cnt' referenced before assignment 

이런 오류가 났다.

 

찾아보니 파이썬은 전역 변수의 데이터를 확인할 수는 있지만 수정할 수는 없기 때문에 전역 변수를 수정하고 싶은 경우 global로 정의를 해줘야 한다고 한다.

반응형

댓글