2143 - 두 배열의 합
📚 2143 - 두 배열의 합
이해
문제에서는 두 배열의 합을 더해서, T가 되는 모든 부 배열의 쌍의 개수를 구하는 프로그램을 작성하려고 하였다.
이는 순차적으로 탐색을 하며, 완전 탐색을 해야하는 상황이다.
배열의 합 : A[i] + ... + A[j]
그 사이의 합을 구하는 문제이다.
순차적으로 탐색을 하며, 사이 구간의 합을 구할 때는 딕셔너리를 사용하면 된다.
이와 같은 문제를 풀 때는, 현재 A의 합들을 딕셔너리에 저장을 한다.
key : 부 배열의 합, value : 횟수
만약에 딕셔너리에 아직 입력된 데이터가 없을 때(횟수가 0일 때는)
딕셔너리.get메서드
를 사용하면 된다.
A
결과를 딕셔너리에 저장을 한 후T - B
가A key
에 존재한다면 갯수 만큼+
을 하면 된다.
소스
import sys
read = sys.stdin.readline
t = int(read())
n = int(read())
a = list(map(int, read().split()))
m = int(read())
b = list(map(int, read().split()))
answer = 0
dist = dict()
for i in range(n):
cur_sum = 0
for j in range(i, n):
cur_sum += a[j]
dist[cur_sum] = dist.get(cur_sum, 0) + 1
for i in range(m):
cur_sum = 0
for j in range(i, m):
cur_sum += b[j]
answer += dist.get(t-cur_sum, 0)
print(answer)
Author And Source
이 문제에 관하여(2143 - 두 배열의 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chang626/2143-두-배열의-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)