BOJ 2143 두 배열의 합

LONGNEW·2021년 1월 28일
0

BOJ

목록 보기
119/333

https://www.acmicpc.net/problem/2143
시간 2초, 메모리 64MB
input :

  • T(-1,000,000,000 ≤ T ≤ 1,000,000,000)
  • n(1 ≤ n ≤ 1,000)
  • A[1], …, A[n]
  • m(1 ≤ m ≤ 1,000)
  • B[1], …, B[m]
  • 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수

output :

-답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력


그 코드포스 문제랑 살짝 비슷한 느낌..
연속적으로 만들수 있는 수의 합을 딕셔너리의 key로 그 값을 만들 수 있는 경우의 수를 value로 넣는다.

그리고 모든 a_dict 에서 t - key 를 한 값이 b_dict 에 있는 지 확인 해서
a_dict 에 있는 경우의 수 * b_dict 에 있는 경우의 수 곱하면 모든 경우의 수이기 떄문에 이렇게 계산을 하자.

처음엔 포인터로 계산을 해야 하나 싶었는데.
경우의 수를 구하는 편이 훨씬 편하다.
요즘에 계속 포인터 나와서 경우의 수 구하는 것을 놓쳤다...

import sys

t = int(sys.stdin.readline())
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
b = list(map(int, sys.stdin.readline().split()))

a_sub, b_sub = {}, {}
for i in range(n):
    temp = 0
    for j in range(i, n):
        temp += a[j]
        if a_sub.get(temp):
            a_sub[temp] += 1
        else:
            a_sub[temp] = 1

for i in range(m):
    temp = 0
    for j in range(i, m):
        temp += b[j]
        if b_sub.get(temp):
            b_sub[temp] += 1
        else:
            b_sub[temp] = 1

ans = 0
for value in a_sub:
    if b_sub.get(t - value):
        ans += (a_sub[value] * b_sub[t - value])
print(ans)

0개의 댓글