BOJ 2143 두 배열의 합

이 문제는 수열이 두 개 주어진다. a수열과 b수열이 주어지면 a수열의 연속된 부분 수열의 합과 b수열의 연속된 부분 수열의 합을 더해서 T가 되는 (a수열의 연속된 부분 수열,  b수열의 연속된 부분 수열) 쌍의 개수를 구하는 문제이다.

T의 제한은 10억까지인데, a, b수열의 길이는 최대 1000이다. 그렇기 때문에 연속된 부분 수열은 1000 * (1000+1) / 2 개, 대략 50만개 정도씩 나온다.
50만개 * 50만개의 모든 경우를 다해보면 바로 시간초과... 그리고 이 문제는 메모리 제한이 32MB로 작은 편인 것도 주의해야할 수도 있다.

생각해봤는데, 일단 a의 연속된 부분합 약 50만 가지 정도를 누적합을 이용해서 구하고 , b의 연속된 부분합 약 50만 가지를 누적합을 이용해서 구하면서 b의 경우, 각 누적합이 몇 개 존재하는지 기록을 해놓는다. 누적합의 범위가 0부터 10억까지이므로 그냥 배열을 사용하면 메모리를 너무 많이 잡아먹기 때문에 map을 이용한다. 그러면 최대 약 50만 가지일 것이다.
일단 아짂까지는 32MB로도 충분하다. 이렇게 구해놓고, 대략 50만 가지의 a의 부분합에 대하여 T == a부분합 + b부분합 이므로 T-a부분합 에 해당되는 (아까 미리 구해놓은)b부분합의 개수를 다 더하면 답을 구할 수 있을 것이다.

한 번 직접 코드로 짜봐야겠다.
오! AC를 받았다! 음 앞서 BOJ 2015 수들의 합4 에서 map을 활용해서 비슷한 방법으로 문제를 풀었기 때문에 이 문제도 풀 수 있었던 것 같다.
근데 시간이 역시 꽤 걸린다. 잘하는 분들 코드 좀 구경하고 백준님의 문제 풀이도 잘 들어봐야겠다.

음... 다른 고수님들 풀이도 보고, 문제 분류도 봤는데 ... 문제 분류는 투 포인터...! 고수님들 풀이도 투 포인터가 많은 것 같다. a, b 배열의 부분합 배열을 sorting해주고 각 부분합 배열에 포인터를 하나씩 두고 처음부터 시작해서 포인터를 하나씩 옮겨가며 T가 되는 경우를 찾아나가는 방식인 것 같다. 그렇게도 풀어 봐야겠다.

-투 포인터 풀이 정리
일단 , 부분합 배열을 sorting하고 a의 부분합 배열의 포인터는 index 0(맨 왼쪽) 부터 시작, b의 부분합 배열의 포인터는 맨 오른쪽부터 시작한다. 그러면서 (부분합 a +부분합 b)의 값을 체크해 나가는 것인데, 이렇게 하면 a의 포인터가 오른쪽으로 가면 (부분합a+부분합b)의 값이 커지고, b의 포인터가 왼쪽으로 가면 (부분합a+부분합b)의 값이 작아지게 된다. 이렇게 T값이랑 같은지 더 큰지 더 작은지 체크해보면서 포인터들을 옮겨주다가 T값이랑 같게되면 T값을 만드는 경우의 수를 세줘야하는데, T값을 만들 수 있는 같은 부분합 요소들이 (sorting을 했기 때문에) 인접해 있기 때문에 a의 부분합 요소 중 같은 값의 개수, b의 부분합 요소 중 같은 값의 개수를 찾아서 그 둘을 곱하면 그 구성요소로 T값을 만들 수 있는 경우의 수를 구할 수 있고, 계속해서 이렇게 T값을 만드는 경우의 수를 찾아서 더해나간다.
주의할 점이 있다면 포인터가 움직이다가 범위를 넘어간다거나 실수해서 무한 루프에 빠지지 않도록 해야한다.