백준 1182번 - 부분수열의 합

출처 : 1182번: 부분 수열의 합 (acmicpc.net)

1182번: 부분수열의 합

 

 

---

 

 

부분 수열의 합 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

256 MB

34899

16084

10187

44.224%

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분 수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 합이 S가 되는 부분 수열의 개수를 출력한다.

 

---

[ 문제 설명 ]

 

이 문제는 그림 한 장으로 설명하는 게 더 빠를 듯하다.

 

그림 1 - 부분수열의 합 문제 해결 아이디어

 

---

 

[ 코드 ]

 

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


def dfs(i, sum):

    global res
    if i == n:
        return
    if sum + numbers[i] == s:
        res += 1

    dfs(i + 1, sum)
    dfs(i + 1, sum + numbers[i])


res = 0
dfs(0, 0)
print(res)

 

---

후기

 

비교적 간단하게 해결할 수 있는 문제.

 

dfs가 익숙하지 않다면 어려울 수 도 있는 문제.