💡 문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
💭 접근
이 문제는 1182번 부분수열의 합 문제와 매우 유사하다.
따라서 1개부터 n개까지 수를 뽑는 조합을 사용하는 로직이 아닌, 각 n개의 숫자가 순서대로 나열되어 있다고 할 때 각각의 숫자를 더할지만 결정해 준다면 총 2개의 경우의 수로도 정답을 구할 수 있다.
즉, 0과 1로 이루어진 n자리 이진수를 사용하여 각 자리가 0인 자리는 더하지 않고, 1인 자리는 더하는 방식으로 부분수열의 합을 구할 수 있다.
그러나 이 문제에선 한가지 제한사항이 있는데, 입력 n의 최대가 20이었던 1182번 부분수열의 합 문제와 달리 해당 문제는 입력 n의 최대가 40이므로 나올 수 있는 경우의 수는 최악의 경우 2개로, 시간초과가 발생한다.
그렇다면 어떻게 해결해야 할까?
단순하게 반으로 나누어, 왼쪽 배열을 계산할 때는 나올 수 있는 부분 배열의 합을 딕셔너리에 저장하고,
오른쪽 배열을 계산할 때는 도출된 부분 배열의 합으로 목표 숫자 s를 뺀 값을 딕셔너리의 키로 가지는 해당 딕셔너리의 값을 더해주면 된다.
코드로 한번 보자.
cnt = 0
if side == LEFT:
for i in range(size):
if tmp[i]:
cnt += arr_left[i]
sums[cnt] += 1위 코드는 왼쪽 배열을 계산하는 부분으로, 왼쪽 배열에서 구한 부분 배열의 합을 sums 딕셔너리에 현재 합을 key로 가지는 value에 1을 더해준다.
이때 value는 부분 배열의 합이 나올 수 있는 경우의 수이다.
elif side == RIGHT:
for i in range(size):
if tmp[i]:
cnt += arr_right[i]
ans += sums[s - cnt]이제 오른쪽 부분이다. 이때는 오른쪽 배열에서 구한 부분 배열의 합으로 목표 숫자 s에서 뺀 값 key로 가지는 딕셔너리의 value를 정답에 더해준다.
이로써 왼쪽 배열과 오른쪽 배열을 더했을 때 목표숫자 s가 나올 수 있는 경우의 수를 더한것이다.
이때 마지막으로 한가지 유의해야 할 것이 있는데,
임의의 이진수 tmp가 모두 0일때는 고려하지 않으므로,
각 왼쪽과 오른쪽 배열에서 부분배열의 합을 구할 때 만약 목표 숫자 s와 같은 값이 나왔다면, 바로 정답에 더해주면 된다.
📒 코드
from collections import defaultdict
LEFT = 0
RIGHT = 1
def dfs(depth, size, side):
global ans
if depth == size:
if tmp == [0] * size:
return
cnt = 0
if side == LEFT:
for i in range(size):
if tmp[i]:
cnt += arr_left[i]
sums[cnt] += 1
elif side == RIGHT:
for i in range(size):
if tmp[i]:
cnt += arr_right[i]
ans += sums[s - cnt]
if cnt == s:
ans += 1
return
for bit in range(2):
tmp.append(bit)
dfs(depth + 1, size, side)
tmp.pop()
n, s = map(int, input().split())
arr = list(map(int, input().split()))
arr_left = arr[:n//2]
arr_right = arr[n//2:]
ans = 0
sums = defaultdict(int)
tmp = []
dfs(0, len(arr_left), LEFT)
dfs(0, len(arr_right), RIGHT)
print(ans)💭 후기
이전에 사용했던 단순한 방법을 두번 사용하여 더 큰 범위의 문제를 해결할 수 있다는 것이 재밌었던 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/1208
