[백준][누적합] 문자열 폭발

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/2143

2143번: 두 배열의 합

 

내가 작성한 코드

import sys
from collections import defaultdict
from collections import deque
read = sys.stdin.readline

def read_data():
    T = int(read().rstrip())
    len_A = int(read().rstrip())
    A = list(map(int, read().rstrip().split()))
    len_B = int(read().rstrip())
    B = list(map(int, read().rstrip().split()))

    return T, A, len_A, B, len_B

def make_accu(A):
    accu_A = [A[0]]
    for i in range(1, len(A)):
        accu_A.append(accu_A[-1] + A[i])

    return accu_A

def get_all_partial_sum(accu_A):
    count_A = defaultdict(lambda: 0)

    for e_i, e in enumerate(accu_A):
        count_A[e] += 1
        for s_i in range(e_i):
            s = accu_A[s_i]
            count_A[e - s] += 1

    return count_A

T, A, len_A, B, len_B = read_data()
accu_A = make_accu(A)
accu_B = make_accu(B)
count_B = get_all_partial_sum(accu_B)

answer = 0
for a_i, a in enumerate(accu_A):
    answer += count_B[T - a]
    for s_i in range(a_i):
        s = accu_A[s_i]
        answer += count_B[T - (a - s)]

print(answer)

• 누적합 배열(make_accu)
  
  • 누적된 배열의 합을 나타내는 배열 만들기
• 부분배열의 합(get_all_partial_sum)
  • 누적합을 이용하여 부분배열이 만들 수 있는 모든 합을 해쉬로 저장
• 해쉬 사용
  • 한 배열에 대한 부분배열의 합 - 목표값의 해쉬를 모두 더하여 출력

 

다른 사람이 작성한 코드

import sys
from _collections import defaultdict

T = int(sys.stdin.readline())

a = int(sys.stdin.readline())
listA = list(map(int, sys.stdin.readline().split()))
b = int(sys.stdin.readline())
listB = list(map(int, sys.stdin.readline().split()))

dictA = defaultdict(int)


ans = 0

for i in range(a):
    for j in range(i, a, 1):
        dictA[sum(listA[i:j+1])] += 1

for i in range(b):
    for j in range(i, b, 1):
        ans += dictA[T - sum(listB[i:j+1])]

print(ans)

• sum을 사용
  
  • 누적합 -> 해쉬를 sum -> 해쉬로 바로 적용하여 간략하게 작성

https://velog.io/@nyanyanyong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98python%EB%B0%B1%EC%A4%80-2143%EB%91%90-%EB%B0%B0%EC%97%B4%EC%9D%98-%ED%95%A9

[알고리즘][python][백준 2143]두 배열의 합

기억해야할 것

• 메모리 초과
  
  • 처음에 두 배열 모두 해쉬로 만들어 메모리 초과
  • 한 배열만 해쉬로 작성하여 통과