목록두 배열의 합 c++ (1)

1일1알

백준 2143번 두 배열의 합 C++

우선 A와 B의 모든 구간에서의 누적합들을 저장하는 벡터를 만든다. A의 누적합과 B의 누적합을 더했을때 t가 되는 경우를 찾으면 되는데, 이분 탐색을 위해 둘중 하나를 정렬한다. 나는 B를 정렬했다. A의 모든 원소를 탐색하면서 B의 원소의 값이 t - A[i]인 경우를 찾으면 되는데, 이때 lower_bound와 upper_bound를 사용했다. lower_bound와 upper_bound는 이분 탐색을 해주는 함수인데, 정렬이 되어있어야 사용이 가능하다. 그래서 앞에서 B를 정렬했다. lower_bound는 찾고싶은 수보다 같거나 큰 인덱스를 반환하고 upper_bound는 찾고싶은 수보다 큰 인덱스를 반환한다. ans에 (upper_bound의 반환값 - lower_bound의 반환값) 을 더해주..
알고리즘 2022. 7. 20. 11:29
이전 Prev 1 Next 다음