class 5

[백준 2143] 두 배열의 합 C++

2143번: 두 배열의 합 첫째 줄에 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)이 주어지고, 그 다 www.acmicpc.net 이분 탐색 1. 문제해결 아이디어 문제에서 정의된 부 배열의 최대 크기는 N(N+1)/2 가 됨을 알 수 있었다. (1~N까지의 합) N, M이 최대 1000이므로 부 배열의 크기는 최대 500,000 이다. 따라서 배열에 담은 후 nlogn 연산이 충분히 가능함을 알 수 있었다. 이분 탐색을 수행하기 위해 subB배열을 정렬한다. T 에서 subA의 원소를 뺀 값이 subB에 있는지 ..