hades

🥅 문제https://www.acmicpc.net/problem/2143 🔍 설계부배열의 형태를 보면, 누적 합을 이용해야 한다는 것은 쉽게 파악할 수 있다.  처음에는 A와 B의 부배열을 구해서 서로 다른 맵에 저장한 후, 한 쪽에서 반복자를 사용해 반복하면서, (T - 한 쪽에 있는 부배열의 합)이 다른 쪽에 있으면, (한 쪽에 있는 부배열의 합의 개수) * (다른 쪽에 있는 부배열의 합의 개수)로 구하려고 했으나 메모리 초과가 발생하였다. 맵 하나가 최대 1000000개 * 2 * 4Bytes 이므로 64MB를 초과하기 때문이었다. 그래서, 맵을 하나만 만들고, 다른 쪽에서 부배열의 합을 만들면서 바로 찾는 방식을 사용하였다. 부배열의 합을 만들기 위해 이중 반복문을 사용하기 때문에 100000..

🥅 설계https://www.acmicpc.net/problem/1920 🔍 분석수의 개수가 최대 100000개이고, 찾으려는 수의 개수가 최대 100000개이므로, 순차 탐색을 할 경우, O(10^10)으로 시간 제한을 초과한다. 따라서, 이분 탐색을 활용한다. 👊 풀이 #include #include #include using namespace std; int n, m, target; vector numbers(100001); bool binary_search(int target){ int start = 0, end = n-1, mid; while (start target) { end = mid - 1; } } return false; } int main() { cin...