두 배열의 합 ( 2143 번 )

2143번: 두 배열의 합

 

🧠 알고리즘

_sum_dict() : 연속 합 몇번 나오는지 딕셔너리로 저장 후 리턴
_main() : 각 부분 합 중 조건에 만족하는 부분 합 경우의 수 증감

 

🧾 코드

import sys

def _sum_dict(n, n_list): # 연속 합 갯수 구하기
    answer = {}
    for i in range(n):
        now_sum = 0
        for j in range(i, n):
            now_sum += n_list[j]
            
            if now_sum not in answer:
                answer[now_sum] = 1
            else:
                answer[now_sum] += 1
    
    return answer


def _main(t, a, a_list, b, b_list):
    answer = 0
    a_sum_dict = _sum_dict(a, a_list)
    b_sum_dict = _sum_dict(b, b_list)

    print(a_sum_dict)
    print(b_sum_dict)
    for k, v in a_sum_dict.items():
        ava_num = (t - k)
        if ava_num in b_sum_dict: # 만족 하는 조건이 있을 시 경우의 수 증감
            answer += (v * b_sum_dict[ava_num])
    
    return answer

t = int(sys.stdin.readline().rstrip())
a = int(sys.stdin.readline().rstrip())
a_list = list(map(int, sys.stdin.readline().rstrip().split()))
b = int(sys.stdin.readline().rstrip())
b_list = list(map(int, sys.stdin.readline().rstrip().split()))

print(_main(t, a, a_list, b, b_list))

 

⏱️ 시간 복잡도

def _sum_dict(n, n_list) : 배열을 순회하며 연속 합 구하기 ( 이차형 시간 복잡도 )
def _main(t, a, a_list, b, b_list) : 조건에 맞는 연속 합 경우의 수 구하기 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )