[BaekJoon] 백준 2143번 : 두 배열의 합

2143번 : 두 배열의 합

처음 풀 땐 가능한 부분합을 모두 구한 뒤 경우의 수를 구했다.

당연히 시간초과가 발생했고 다른 사람들의 풀이를 참고했다..

해결방법은 부분합을 사전에 저장한 뒤 가능한 경우의 수를 구하면 된다.

defaultdict 를 사용했었는데 메모리 초과가 발생 해 try except 로 사전을 생성했다.

이 외 다른 방법으로는 a 배열의 부분합만 defaultdict 로 만들고

b 배열의 부분합을 저장하는 과정에서 바로 답을 도출하면 메모리 초과도 없고 시간도 더 빠르게 해결할 수 있다.

---

import sys


def solution():
    T = int(sys.stdin.readline())
    a_len = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().rsplit()))
    b_len = int(sys.stdin.readline())
    b = list(map(int, sys.stdin.readline().rsplit()))

    # 1. a의 연속합을 저장한다.
    a_sum = dict()
    for i in range(a_len):
        for j in range(i, a_len):
            try:
                a_sum[sum(a[i:j + 1])] += 1
            except KeyError:
                a_sum[sum(a[i:j + 1])] = 1

    # 2. b의 연속합을 저장한다.
    b_sum = dict()
    for i in range(b_len):
        for j in range(i, b_len):
            try:
                b_sum[sum(b[i:j + 1])] += 1
            except KeyError:
                b_sum[sum(b[i:j + 1])] = 1

    # 3. 경우의 수를 구하는 것이기 때문에 곱셈으로 계산한다.
    answer = 0
    for key in a_sum:
        try:
            answer += b_sum[T - key] * a_sum[key]
        except KeyError:
            continue

    return answer


if __name__ == "__main__":
    print(solution())