[BaekJoon] 2143 두 배열의 합

🔦 문제 링크

✍️ 딕셔너리 풀이

---

• 원소가 자연수가 아닌 음수가 가능한 정수이다.
• 따라서, 이전 투 포인터 문제와 같이 푸는 것은 불가능하다.
• 각자의 모든 조합을 구해( $O(2^(1000))$ ) 더해보는 것은 시간이 엄청 많이 걸린다.

< 풀이 순서 >

• 모든 부분합은 $O(n^2)$으로 처리 가능하다.

1. 딕셔너리에 모든 부분합의 갯수를 기록한다.
2. 한쪽 딕셔너리의 값을 가져와 다른 딕셔너리 뺀 값이 존재하면 두 딕셔너리의 합은 T 이다.
3. 조합의 수는 중복된 합의 개수를 서로 곱하면 된다.

🛠 딕셔너리 코드

---

t = int(input())
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))

a_dic = dict()
b_dic = dict()

for i in range(n):
    sm = 0
    for j in range(i, n):
        sm += a[j]
        if not a_dic.get(sm):
            a_dic[sm] = 1
        else:
            a_dic[sm] += 1  #  같은 합의 갯수를 셀 수 있다.

for i in range(m):
    sm = 0
    for j in range(i, m):
        sm += b[j]
        if not b_dic.get(sm):
            b_dic[sm] = 1
        else:
            b_dic[sm] += 1

result = 0
for a_val in a_dic:
    if b_dic.get(t - a_val):
        result += a_dic[a_val] * b_dic[t - a_val]

print(result)

✍️ Bisect 풀이

---

• 똑같이 부분합을 $O(n^2)$의 시간복잡도로 전처리 해준다.

< 풀이 순서 >
1. Bisect를 사용하기 위해 사용할 부분합 리스트를 정렬해준다.
2. (목표값 - a)인 b 가 존재하면 해당 값의 중복 갯수를 세준다.
3. 이를 결과값에 더해준다.

🛠 Bisect 코드

---

import bisect

t = int(input())
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
a_sum, b_sum = [], []

for i in range(n):
    sm = 0
    for j in range(i, n):
        sm += a[j]
        a_sum.append(sm)

for i in range(m):
    sm = 0
    for j in range(i, m):
        sm += b[j]
        b_sum.append(sm)

b_sum.sort()
count = 0
for a in a_sum:
    upper = bisect.bisect_right(b_sum, t - a)
    lower = bisect.bisect_left(b_sum, t - a)
    count += (upper - lower)
print(count)

📝 정리

---

• 부분합을 $n!$ 만에 구할 수 있어야 한다.
• 딕셔너리를 통해 중복된 값의 수를 표현한다.
• Bisect를 통해 중복된 값의 수를 표현한다.

🎈 참고

---

suri78님 블로그