[BOJ] 2143 두 배열의 합

2143번: 두 배열의 합

문제

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

T(=5) = A[1] + B[1] + B[2]
      = A[1] + A[2] + B[1]
      = A[2] + B[3]
      = A[2] + A[3] + B[1]
      = A[3] + B[1] + B[2]
      = A[3] + A[4] + B[3]
      = A[4] + B[2] 

입력

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

출력

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

---

 

solved.ac의 class5에서 고른 문제를 풀었다. 이분 탐색을 활용하는 문제였는데 class5에 이분 탐색 문제가 꽤나 많은 것 같다. 

 

지금까지 풀었던 이분 탐색 문제는 대부분 직접 while 문을 이용하는 편이였다. 얼마 전에 공부했던 매개 변수 탐색 같은 유형도 while 문을 직접 작성해서 문제를 해결했다. 반면, 이번 문제는 upper, lower bound 함수를 사용했다. 내가 스스로 생각해낸 것은 아니고 문제를 풀다 시간 초과를 해결할 방법이 딱히 떠오르지 않아서 다른 분들의 정답을 참고했다. 

 

문제를 해결하기 위한 첫번째 아이디어는 부분합을 미리 모두 구해놓는 것이다. 이때 배열의 최대 크기가 1000이므로 부분합이 최대 1000*1001/2(약 50만)개일 수 있다. 부분합을 구하는 부분은 O(N^2) 이지만 N이 최대 1000이므로 시간 안에 충분히 가능하다. 그리고 두번째 아이디어는 부분합을 오름차순으로 정리해놓는 것이다. 부분합들은 정렬되어 있다고 전혀 보장할 수 없는 상태로 저장되어 있다. 어차피 문제에서 부분합의 인덱스 같은 정보를 원하는 것이 아니므로 정렬해도 상관 없다. 이때 1개의 벡터만 정렬이 필요하다.

 

마지막 아이디어는 정렬되어 있는 벡터에서 다른 벡터의 한 값에 대해 upper bound와 lower bound를 구한다. 각 인덱스 사이에 있는 값들은 모두 조건을 만족하기 때문에 정답에 더해주면 된다. upper bound와 lower bound는 찾는 원소가 없는 경우엔 end() 값을 리턴하기 때문에 단순하게 작성해도 프로그램에 문제가 생기지 않았다.

 

후기)

오랜만에 백준 문제를 풀어서 마음이 편안해진다....