Coding 공부

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()

T = int(input())

N = int(input())
A_arr = [0] + list(map(int,input().split()))

M = int(input())
B_arr = [0] +list(map(int,input().split()))


for i in range(N):
    A_arr[i+1] += A_arr[i]

for j in range(M):
    B_arr[j+1] += B_arr[j]

A_nums = defaultdict(int)
B_nums = defaultdict(int)
for i in range(1,N+1):
    for j in range(i):
        A_nums[A_arr[i] - A_arr[j]] += 1

for i in range(1,M+1):
    for j in range(i):
        B_nums[B_arr[i] - B_arr[j]] += 1

result = 0
for num in A_nums:
    find_num = T -num
    if B_nums.get(find_num):
        result = result + A_nums[num] * B_nums[find_num]

print(result)

이 문제는 누적합을 이용해 풀었다. 이 문제는 다음과 같다. 두 배열이 주어지고,

두 배열의 원소들을 더해서 T가 나올 수 있는 경우의 수를 구하는 문제이다.

그래서 먼저 사전 작업을 해주었다.

각 배열들을 전부 누적합을 통해 특정 구간의 전체 합을 구하기 쉽게 만들어줬다.

이렇게 누적합을 미리 준비해주고,

j ->i 까지의 나올수 있는 모든 종류의 부분 합을 dict 에 저장을 해준다.

이렇게 사전 준비 작업을 했으면,

A_nums 라는 A 배열에서 나올 수 있는 모든 부분 배열의 합의 종류들의 key 값으로 탐색을 해준다.

T 에서 A에서 나올 수 있는 배열의 합을 뺀 값이 B에 존재 하면,

이 두 배열의 값들로 만들 수 있는 경우의 수는 A_nums[num] * B_nums[find_num]이 된다.

이 값들을 구해서 결과 값을 출력해주면 된다.

import sys

input = sys.stdin.readline

N = int(input())

M = int(input())
S = [0]*N
E = [0]*N
for _ in range(M):
    x, y = map(lambda x : x-1 ,list(map(int,input().split())))

    S[x] += 1
    E[y] += -1




ind = 0
result = 0
big_cnt = 0
while ind<N:
    if big_cnt:
        big_cnt += S[ind] + E[ind]
        if big_cnt == 0:
            result += 1
        ind += 1
    else:
        if S[ind] == 0:
            result += 1
        else:
            big_cnt += S[ind]
        
        ind += 1
print(result)