문제 풀이

백준 18114번 블랙 프라이데이 문제와 살짝 비슷하다고 생각이 들었다.

어떤 수(A)를 만들지 선택하고 A를 만드는 두 개의 수의 조합을 찾으면된다. 두 개의 수 중 하나는 for문, 다른 하나는 (A에서 for문에서 고른 수를 뺀 수) 이분탐색으로 찾으면 O($N^2$logN)으로 풀 수 있을것 같았다.

블랙 프라이데이 문제와 다른점은 다른 수와 같은 수가 있을 수도 있다는 것과 음수도 존재할 수 있다는 것이었다.

그러므로 두 개의 수를 찾을때는 한 개는 배열 전체에서, 다른 한 개의 수는 이분 탐색으로 l=0, r = j-1로 잡고 찾으면된다.
단, 만들려는 수와 선택한 수가 겹치면 안되고, 고르는 수 또한 중복으로 선택하면 안되므로
i==j, mid ==i , mid ==j 같은 상황은 예외처리해주면 된다.

문제 링크

boj/1253

소스코드

PS/1253.java

       import java.io.*;
    import java.util.*;


    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        public static void main(String[] args) throws IOException {
            int n = Integer.parseInt(br.readLine());

            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr);
            int cnt = 0;
            for (int i = n - 1; i >= 0; i--) {
                int val = arr[i];
                boolean flag= false;
                    for (int j = n-1; j >= 0; j--) {

                        int l = 0;
                        int r = j - 1;
                        if(j == i)
                            continue;
                        while (l <= r) {
                            int mid = (l + r) / 2;
                            int val2 = val - arr[j];
                            if (arr[mid] > val2) {
                                r = mid - 1;
                            } else if (arr[mid] == val2 && mid != i && mid != j) {
                                flag = true;
                                break;
                            } else {
                                l = mid + 1;
                            }
                        }

                    }
                    if (flag)
                        cnt++;
            }
            bw.write(Integer.toString(cnt));
            bw.flush();
        }


    }