[BOJ][2143] 두 배열의 합

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

---

투 포인터(Two-Pointer)를 이용하여 풀었습니다.
배열 당 모든 부배열을 만드는 시간 복잡도는 O(n2)인데 n의 크기가 (1<= n <= 1000) 이므로 시간 내에 배열 A, B의 부배열의 합들을 구할 수 있습니다.

1. 각 배열의 모든 부 배열들을 구하여 subA, subB에 넣습니다.
2. subA, subB를 오름차순 정렬합니다.
3. subA를 왼쪽(L)부터, subB를 오른쪽(R)부터 탐색합니다.
4. subA[L] + sub[R]을 sum이라고 봤을 때
4-1. sum < T 라면 sum의 크기를 더 키워야 하므로 L++ 해줍니다.
4-2. sum > T라면 sum의 크기를 작게해야 하므로 R-- 해줍니다.
4-3 sum==T 라면 각 배열에서 subA[L], subB[R]과 같은 수의 개수를 세고 구한 수를 곱한 것을 정답에 더해줍니다. 그리고 다음 수를 탐색해야 하므로 L++, R-- 해줍니다.
5. 4번을 L과 R이 각 배열의 인덱스 값을 넘어가기 전까지 반복합니다.

---

문제의 예제를 가지고 예를 들어 보겠습니다.

A = {1,3,1,2}로 만들 수 있는 부 배열의 합들을 구한 뒤 subA에 넣고 오름차순해줍니다.
B = {1, 3, 2}도 마찬가지로 부 배열들의 합을 구한 뒤 subB에 넣고 오름차순해줍니다.
이제 subA는 작은 수부터 subB는 큰 수부터 탐색하고자 subA의 인덱스를 나타내는 변수 L은 1으로 subB의 인덱스를 나타내는 R은 6으로 세팅합니다.
실제로 배열의 시작인덱스는 0이지만 여기서는 보기 쉽게 1을 시작인덱스로 보겠습니다.

1+6 = 7 (>T) 이므로 R--해줍니다. (L=1 / R=6)
1+5 = 6 (>T) 이므로 R--해줍니다. (L=1 / R=5)
1+4 = 5(==T) 이므로 subA에서 1의 개수 x subB에서 4의 개수를 구하면 2x1 = 2가 됩니다. 곱하는 이유는 부 배열 쌍의 개수를 구하는 것이기 때문입니다. 해당 수를 정답에 더하고 L++, R-- 해줍니다. (L = 1, 2 / R = 4)

2+3 = 5 (==T) 이므로 subA에서 2의 개수(1) x subB에서 3의 개수(1)의 값을 정답에 더하고 L++, R-- 해줍니다. (L=3 / R=3)

3+2 = 5 (==T) 이므로 subA에서 3의 개수(2) x subB에서 2의 개수(1)의 값을 정답에 더하고 L++, R-- 해줍니다. (L=4, 5 / R=2)

4+1 = 5 (==T) 이므로 subA에서 4의 개수(2) x subB에서 1의 개수(1)의 값을 정답에 더하고 L++, R-- 해줍니다. (L=6, 7 / R=1)

이 때, R= 0 (<1) 이 되므로 배열의 인덱스 값을 벗어나므로 이때까지 구한 정답을 출력해줍니다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/BOJ/2143.%20%EB%91%90%20%EB%B0%B0%EC%97%B4%EC%9D%98%20%ED%95%A9.cpp