백준 2143. 두 배열의 합

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

2143번: 두 배열의 합

 

 

1. A와 B에 대해 배열의 요소를 1개 선택, 2개 선택, ... , N개 선택했을때의 누적합을 구한다.

구하는 방법은 cnt개 선택이라면 [arr[0], arr[cnt-1]) 까지의 합 sum을 구하고,

다음 인덱스로 이동하면서 sum에서 arr[i] 값은 더해주고 arr[i-cnt] 값은 빼준다.

이렇게 하면 O(N*N)이 아닌 O(N)에 구할수 있다. 

 

2. 구한 A의 누적합들은 Asum에, B의 누적합들은 Bsum에 저장하고 이분탐색을 위해 오름차순 정렬한다.

Asum[i] 를 기준으로 합이 T가 되려면 Bsum에서 찾아야 하는 값은 T - Asum[i] 일것이다.

lower_bound() 로 Bsum에 해당 값이 시작하는 인덱스, upper_bound()로 해당 값이 초과하는 인덱스를 찾으면 두 인덱스의 차이가 우리가 찾는 값이 몇개있는지를 나타내고 이를 Bcnt 라고 하자.

Asum[i] 이 몇개인지도 동일하게 찾아주고 ACnt라고 하자.

 

3. 그러면 Asum[i] + Bsum[i] = T 이고,

Asum[i]의 갯수는 Acnt개, 

Bsum[i]의 갯수는 Bcnt개 이므로 

쌍의 갯수는 Acnt * Bcnt 개 이다. 

 

 

주의할점은 A,B의 누적합들을 저장한 Asum, Bsum의 길이는 최대 50만이다. 

A에서 요소 1개의 누적합은 누적합의 갯수는 1000개가 나오고, 2개의 누적합은 갯수 999개 나오고 ... 1000개 누적합은 1개가 나온다. 

(1 + 2 + ... + 1000) = 50만쯤된다.

따라서 Acnt * Bcnt 는 int 범위를 넘기 때문에 주의해야 한다.