백준: 2143 두 배열의 합

문제

2143번: 두 배열의 합

 

문제 풀이

 앞 서 다룬부분수열의 합 2와 유사한 문제이다. 부분수열의 합 2 문제는 입력되는 순열을 직접 절반으로 나누어 처리하여야 하지만, 해당 문제는 이미 A, B라는 배열을 나누어서 입력된다. 입력되는 배열을 합 중, T와 일치하는 경우가 있는지 판단하고 반환하는 문제이다.

 

부분수열의 합 2 문제와 동일한 로직을 통해 문제를 해결할 수 있다. 앞의 문제 처럼 배열 A에 대해 부분합을 딕셔너리를 통해 카운트하고, 배열 B에서는 t - B의 부분합이 있다면 정답으로 반영하도록 하였다.

 

코드

from sys import stdin
from collections import defaultdict


def subtotal(lst, length, direction):
    global answer

    for i in range(length):
        cur_subtotal = 0
        for j in range(i, length):
            cur_subtotal += lst[j]
            if direction == "left":
                subtotal_a[cur_subtotal] += 1
            else:
                answer += subtotal_a[t - cur_subtotal]


if __name__ == "__main__":
    answer = 0
    subtotal_a = defaultdict(int)
    t = int(stdin.readline())
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    m = int(stdin.readline())
    b = list(map(int, stdin.readline().split()))
    subtotal(a, n, "left")
    subtotal(b, m, "right")
    print(answer)