dh_0e

누적 합과 이분 탐색으로 쉽게 풀 수 있는 문제lower_bound, upper_bound 오랜만에 직접 구현해보다가 결국 귀찮아서 라이브러리에 있는 거 썼다.. 풀이 과정누적 합으로 A, B 배열의 부 배열의 합이 될 수 있는 경우의 수를 모두 vector에 저장해준다. (최대 500500 경우의 수)둘 중 하나를 sort 해준다.upper_bound - lower_bound로 target(t - vec_a[i])이 몇 개나 있는 지 구해서 dap에 더해준다.dap은 int 범위를 넘을 수 있으므로 long이나 long long으로 처리해준다.못 찾았을 경우 up, lo 모두 end() 저장소의 위치를 가르키므로 예외처리 안 해줘도 0을 더한다. #include#include#includeusing n..

구현은 매우 쉽지만 발상하는데 시간이 꽤 걸렸던 문제A B의 합, C D의 합을 모두 구한 배열(각각 최대 1600만) 2개를 만든 뒤 정렬하여 two pointer, binary search를 사용하여 합이 0인 쌍의 개수를 구하면 된다. #include#include#includeusing namespace std;typedef long long ll;vector vec1, vec2;ll a[4001], b[4001], c[4001], d[4001];int binary_search(int en, int target) { int st = 0; while (st 0) n2--; else n1++; } printf("%lld\n", dap); return 0;}

2023 UCPC 예선 K번 문제로, 처음엔 그리디 + 우선순위 큐를 사용하여 시도해 봤지만, 큐가 정렬이 되는 기준을 잡는 것이 힘들었을뿐더러, $a_{i}$값이 중복되는 경우에 항상 답을 도출한다는 보장이 없었다. 해결 방법 답으로 출력될 세미나 수의 최솟값($c$)에 대하여 이분 탐색으로 접근해서 bst 함수에서 그리디하게 $i$번째 세미나의 시작 시간을 정한다. 이때 로직은 $c$가 답으로 도출될 수 있게끔 세미나의 시작 시간을 최대한 빠르게 지정한다 (물론 $a_{i}$가 속하게끔). 이후 모든 세미나의 범위에 $a_{i}$가 속하는지 확인하여 true or false를 반환한다. 반환한 값을 바탕으로 이분 탐색이 끝나면 세미나 수의 최솟값을 구할 수 있으며 이분 탐색 + 그리디로 $O(nlog..