부분 합. [2143]

[1. 문제 설명]

https://www.acmicpc.net/problem/2143

---

[2. 풀이 접근]

부분 합, 이진 탐색을 조합하여 풀 수 있는 문제이다.

 

하나의 배열에서 부 배열의 모든 합의 조합은 최대 10⁶ 개 이다.

• 여기서 중복된 값은 제거하면 안된다.
• 합이 같아도, 부 배열을 이루는 원소가 다르거나, 부 배열을 이루는 원소의 위치가 다르기 때문이다.
• 즉, 각 경우가 고유한 조합이기 때문이다.

즉, 두개의 배열에서 각 부 배열의 합의 조합은 최대 10¹² 개 이다.

• 정답 출력을 위해서는 8byte 크기의 정수형 변수를 사용해야 한다.
• 중첩 for 문으로 구하면 시간 초과가 발생하니, 좀 더 빠른 탐색을 고민해야 한다.

---

부분 합

• 부 배열의 합을 O(1) 에 구할 수 있다.
• O(N^2) 에 부 배열의 모든 합의 조합을 구할 수 있다. 

이진 탐색

• 하나의 부 배열의 모든 합의 조합을 순차 탐색 할 때,
• 다른 하나의 부 배열 합의 조합은 이진 탐색으로 T 를 만드는 값을 빠르게 구할 수 있다.

---

[3. 코드]