[백준] 2143번 두 배열의 합 (Python)

백준 2143 두 배열의 합

문제 자체가 어렵진 않았지만, 메모리 제한이 64MB로 조금 빡빡한 편이었다. 리스트 A, B 두 리스트를 선언하고, 부분 합을 모두 dict에 넣어봤지만, 시간 초과가 났다. 결국 A 리스트의 부분합을 dict에 넣고 B 리스트를 2중 for 문으로 가능한 모든 경우를 탐색하여 메모리를 아꼈다. 합을 저장한 리스트에서 모든 index의 차이는 부분합이 된다는 점을 활용하여 부분합을 구했다. 따라서 0을 첫 번째 인덱스로 넣어줌으로써 첫 인덱스부터 더해지는 부분합 또한 구할 수 있어야 한다. 이 문제의 중요한 포인트는 아래와 같다.

1. A 리스트에 0부터 해당 인덱스까지의 합을 리스트에 저장한다.
2. A 리스트를 탐색하면서 부분 합을 구하고 해당 부분 합의 개수를 dict에 저장한다.
3. B 리스트 또한 같은 과정을 통해 부분 합을 저장하고, 매 인덱스마다 2중 for 문을 통해 aDict에 필요한 값의 개수를 확인하여 결괏값에 더한다.

import sys

def Solution():
    inp = sys.stdin.readline
    target = int(inp())
    n = int(inp())
    aDict = dict()
    aList = [0]
    s = 0
    for num in map(int, inp().split()):
        s += num
        aList.append(s)

    for i in range(n):
        for t in range(i + 1, n + 1):
            if (tmp := aList[t] - aList[i]) in aDict:
                aDict[tmp] += 1
            else:
                aDict[tmp] = 1
    del(aList)

    m = int(inp())
    bList = [0]
    s = 0
    res = 0
    for num in map(int, inp().split()):
        s += num
        for b in bList:
            if (tmp:= target - (s - b)) in aDict:
                res += aDict[tmp]
        bList.append(s)
    return res

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