[Algorithm] 백준_2143번: 두 배열의 합

오늘의 문제는 🚀 백준 2143 두 배열의 합이다.

어렵다. 컴비네이션을 풀어야 하는줄 알고 끙끙 풀다가 시간이 너무 많이 지나버려서.. 😂 다른 분의 풀이를 참고했다.

테스트케이스 이해하기

부배열이 배열 속의 일정 범위 연속된 값이라는 것을 제대로 이해하지 못했다..

그냥 부분집합이라고 생각했는데.. 문제를 똑바로 읽자!

그래서 연속된 일정 범위의 각각의 배열들의 부배열의 합이 첫번째로 들어온 값이 되는 경우가 몇가지 인지 찾는 것이다.

알고리즘

1. input을 받고 각 배열의 부분합을 더해줄 딕셔너리 두개를 선언한다.
2. 이중 for문과 sum 함수를 사용해서 각각 배열의 부분합들을 구해 준다. (key는 총 부분합의 값, value는 부분합의 갯수)
3. 한 딕셔너리 값을 돌면서 T-key , key의 짝을 맞추어 숫자를 곱해서 결과값에 더해준다. ⇒ 총 갯수 구하기

p.s 딕셔너리를 좀 더 익숙하게 쓰는 걸 연습해야겠다. 그리고 파이썬 내장 함수도 익숙해지자!

정답코드

import sys
from collections import defaultdict

input = sys.stdin.readline

T = int(input())
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))

A_sum = defaultdict(int)
B_sum = defaultdict(int)

for i in range(N):
    for j in range(i, N):
        A_sum[sum(A[i:j+1])] += 1

for i in range(M):
    for j in range(i, M):
        B_sum[sum(B[i:j+1])] += 1

answer = 0
print(A_sum)
print(B_sum)

for key in A_sum.keys():
    answer += B_sum[T - key] * A_sum[key]
print(answer)

출처: 동학 개발 운동 블로그

🚀Reference: 백준 2143 두 배열의 합