백준 2143 두 배열의 합 - 파이썬
접근, 사고
확실히 푼 문제 수가 쌓일수록 유형별로 나눠서 생각하기가 수월한것 같다.
이 유형의 베이스는 Two Sum 이다 (무려 리트코드의 첫번째 문제!!).
배열을 탐색하며 두 개의 합의 target 이 되는 쌍을 찾는 문제인데 해쉬를 이용해 한 번 linear 로 훑는 것으로 풀 수 있다. 대략적인 풀이과정은
- set 선언
- 배열 지나가며 각각 원소 i에 대해 target - i 가 set 에 있으면 해당 쌍 리턴, 없으면 set.add(i) 해준다.
본 문제도 이와 크게 다르지 않다.
앞서 유형별로 나눠 접근하기가 수월하다고 했던 것은 똑같이 합을 찾는 문제여도 근사치를 찾는 문제와 정확히 target을 찾아야 하는 문제는 필요한 알고리즘이 아예 다르다.
간단한 문제를 직접 마주해보는만큼 좋은 체험은 없다.
import sys
from collections import defaultdict
input = sys.stdin.readline
def solve():
T = int(input())
A = int(input())
a = [int(x) for x in input().split()]
B = int(input())
b = [int(x) for x in input().split()]
d = defaultdict(int)
for i in range(len(a)):
s = 0
for j in range(i, len(a)):
s += a[j]
d[s] += 1
cnt = 0
for i in range(len(b)):
s = 0
for j in range(i, len(b)):
s += b[j]
if T - s in d:
cnt += d[T - s]
print(cnt)
if __name__ == '__main__':
solve()
