13. 부분수열의 합
-
부분 수열의 합
- N개의 정수로 이루어진 수열이 있을 때,
- 길이가 양수인 부분 수열 중에서, 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램 작성
어려웠던 점
- 직관적으로 와닿지가 않아서 좀 어려웠다.
- {1,2,3}이 있다고 했을 때,
- 각 원소를 트리로 구성해보면 ( 결과적으로 DFS를 만들려면 트리 모양이 나와야한다)
-
1을 더할지 말지, 그리고 또 2를 더할지말지로 -> 트리모양으로 구성이된다.
def DFS(s):
global result
global currentSum
if s == N:
return
if currentSum + arr[s] == S:
result += 1
DFS(s+1) # 이번 원소 포함시키지 않고 시도
currentSum += arr[s]
DFS(s+1) # 이번 원소 포함시키고 시도
currentSum -= arr[s]
N, S = map(int, input().split())
arr = list(map(int, input().split()))
currentSum = 0
result = 0
DFS(0)
print(result)
다르게 바라보기?
- 똑같지만 프로그래머스 타겟넘버에서 푼 것처럼 풀 수 없을까?
- 타겟넘버는 무조건 더하거나 뺀다는 선택지가 두개밖에 없었다. 하지만 부분수열의 합 같은 경우, 더하지 않고 그냥 지나친다는 선택지가 있기에 구현 방식이 다르다고 할 수 있다.
참고자료