반응형
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로 정의를 해줘야 한다고 한다.
반응형
'알고리즘 > 백트래킹' 카테고리의 다른 글
[백준][Python] 18429번 근손실 (0) | 2022.08.08 |
---|---|
[백준][Python] 10974번 모든 순열 (0) | 2022.08.04 |
[백준][Python] 15652번 N과 M (4) (0) | 2022.08.01 |
[백준][Python] 15651번 N과 M (3) (0) | 2022.08.01 |
[백준][Python] 15650번 N과 M (2) (0) | 2022.07.29 |
댓글