[BaekJoon] 1208 부분수열의 합 2

🔦 문제 링크

✍️ 풀이

---

• $2^{20}$ 은 $10^6$, $2^{40}$ 은 $10^{12}$
• 1억은 $10^8$ (시간복잡도 계산 시 사용)
• 40개의 모든 조합을 만들기 위해선 $O(2^{40})$ 만큼이 필요하다.
• 따라서 조합을 반절 씩 나눠 모든 조합을 구하고 그 합을 투 포인터로 구해서 답을 구한다.

combination의 범위를 mid+1 해줘야 한다. (인덱스는 0부터 시작)

🛠 나의 코드

---

from itertools import combinations
n, s = map(int, input().split())
arr = list(map(int, input().split()))

mid = len(arr) // 2
arr_l = arr[:mid]
arr_r = arr[mid:]
le, ri = dict(), dict()
for i in range(mid+1):
    lecom = combinations(arr_l, i)
    for com in lecom:
        sm = sum(com)
        if not le.get(sm):
            le[sm] = 1
        else:
            le[sm] += 1

for i in range(len(arr)-mid+1):
    recom = combinations(arr_r, i)
    for com in recom:
        sm = sum(com)
        if not ri.get(sm):
            ri[sm] = 1
        else:
            ri[sm] += 1

result = 0
for lval in le:
    if ri.get(s - lval):
        result += (ri[s - lval] * le[lval])

print(result-1 if s == 0 else result)

📝 정리

---

• 부분수열의 합이 0이 될 때 답에 -1을 해줘야 한다.
• 조합을 구할 때 공집합 두개를 더하면 0이 나오기 때문이다.
• 하지만 원하는 합이 0이 아닐 때는 빼줄 필요가 없다.

🎈 참고

---

suri78님 블로그