Python을 이용한 2143번 : 두 배열의 합 에 대해서 포스팅하겠습니다. 2143번은 브루트포스 자료 구조, 이분 탐색, 누적 합의 알고리즘으로 분류되는 문제입니다.
1. 2143번 문제설명
- 입력:
- 첫 번째 줄에 학생의 수 N이 주어집니다.
- 두 번째 줄에 N명의 학생들의 코딩 실력 Ai가 공백으로 구분되어 주어집니다.
- 출력:
- 코딩 실력 합이 0이 되는 3인조 팀의 수를 출력합니다.
2. 2143번 접근방법
2-1. 부분 배열 합 계산
- 먼저, 배열 A와 B 각각에 대해서 가능한 모든 부분 배열의 합을 계산합니다. 예를 들어, 배열 A가 [1, 3, 1, 2]라면, 가능한 부분 배열 합은 1, 4(1+3), 5(1+3+1), 7(1+3+1+2), 3, 4(3+1), 6(3+1+2), 1, 3(1+2), 2 등이 있습니다. 이 계산은 각 배열에 대해 두 번의 반복문을 사용하여 모든 가능한 시작점과 끝점의 조합으로 부분 배열을 만들고, 그 합을 계산함으로써 이루어집니다.
2-2. 해시 맵 사용
- 각 부분 배열의 합을 저장할 때는 해시 맵을 사용합니다. 이는 각 합을 키로, 그 합을 만들 수 있는 부분 배열의 개수를 값으로 가집니다. 예를 들어, 배열 A에서 합이 4인 부분 배열이 2개 있다면, 해시 맵에는 {4: 2}와 같은 항목이 저장됩니다. 이 방법을 사용하면 나중에 특정 합을 빠르게 찾아내고 그 개수를 알 수 있습니다.
2-3. 목표 합 T와 비교
- 배열 A와 B에서 계산된 부분 배열의 합을 가지고 있는 두 개의 해시 맵이 준비되면, A의 합 하나하나를 살펴보며 T에서 그 값을 뺀 결과가 B의 해시 맵에 존재하는지 확인합니다. 예를 들어, T가 5이고 A의 부분 배열 합 중 하나가 2라면, B의 해시 맵에서 3(5-2)이 존재하는지를 확인합니다. 존재한다면, 그 합을 만들 수 있는 부분 배열의 개수를 A의 해당 합의 개수와 곱하여 쌍의 수를 구합니다.
2-4. 결과 계산
- 위 과정을 모든 A의 부분 배열 합에 대해 반복하며, 가능한 모든 쌍의 수를 더합니다. 이렇게 해서 최종적으로 T를 만들 수 있는 모든 부분 배열 쌍의 개수를 찾아낼 수 있습니다.
3. 2143번 코드
Python
# https://www.acmicpc.net/problem/2143
from sys import stdin
from collections import defaultdict
# 목표값과 배열의 크기 및 요소를 입력 받음
target = int(stdin.readline())
a_size = int(stdin.readline()) # 배열 A의 크기 입력 받기
a = list(map(int, stdin.readline().split())) # 배열 A 입력 받기
b_size = int(stdin.readline()) # 배열 B의 크기 입력 받기
b = list(map(int, stdin.readline().split())) # 배열 B 입력 받기
# 주어진 배열의 모든 부분합을 계산하는 함수
def calculate_subsums(arr):
sums = defaultdict(int) # 부분합을 저장할 defaultdict 생성
for i in range(len(arr)): # 배열의 모든 요소에 대해 반복
current_sum = 0 # 현재 부분합 초기화
for j in range(i, len(arr)): # 현재 위치부터 배열의 끝까지 반복
current_sum += arr[j] # 현재 위치의 값 더하기
sums[current_sum] += 1 # 현재 부분합의 개수 증가
return sums # 계산된 부분합 반환
# 각 배열에 대해 부분합 계산
a_subsums = calculate_subsums(a)
b_subsums = calculate_subsums(b)
# 목표값을 만들 수 있는 조합의 수를 찾습니다.
count = 0 # 조합의 수를 저장할 변수를 0으로 초기화합니다.
for subsum in a_subsums: # 배열 A의 모든 부분합에 대해서 반복합니다.
# A의 부분합이 x일 때, 목표값 T에서 x를 뺀 값(T - x)가 배열 B의 부분합 중에 존재하는지 확인합니다.
# 존재한다면, 이는 A의 부분 배열의 합과 B의 부분 배열의 합을 합쳐서 목표값 T를 만들 수 있는 하나의 경우를 의미합니다.
if target - subsum in b_subsums:
# A와 B의 해당 부분합의 조합의 수를 곱해주어야 합니다.
# 이는 A의 부분합이 x인 조합의 수와 B의 부분합이 T-x인 조합의 수를 곱함으로써,
# T를 만들 수 있는 모든 가능한 A와 B의 부분 배열 조합의 수를 계산하기 위함입니다.
count += a_subsums[subsum] * b_subsums[target-subsum] # 조합의 수를 업데이트합니다.
# 최종적으로 계산된 조합의 수를 출력합니다.
print(count)