문제링크

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

구현방법

• • N개의 수

    • N 은 최대 2000개

숫자의 범위는 -1000000000 ~ 1000000000



어떤 수가 다른 두 수의 합으로 나타낼 수 있다면 good

수의 위치가 다르면 값이 같아도 다른 수.



정렬이 필요한가?

- 어떤 수가 다른 두 수의 합으로 나타 낼수 있다면 이기 때문에
- 모든 수의 대한 계산이 필요하지 않을까 -> 정렬을 통해서 계산이 필요할 거 같다.



각 숫자에 대한 이분탐색을 통해서 해당 숫자를 만들수 있는지 확인하는 작업을 진행

- 이분탐색의 시간복잡도는 O(logN)이기 때문에 모든 계산보다 훨씬 빠름.



각 숫자를 만들수 있는지 이분탐색을 통해서 계산하면 끝인 문제이다.

알고리즘

• 이분 탐색

CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int number[] = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int idx = 0; idx < N; idx++) {
            number[idx] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(number);

        int res = 0;

        //전체 숫자 확인
        for (int idx = 0; idx < N; idx++) {
            int choice = number[idx];
            int left = 0;
            int right = N - 1;
            while (left < right) {

                //같은 수가 나오면안되기 때문에 바꿔주기
                if (left == idx) left++;
                else if (right == idx) right--;

                //만약 둘이 같은 곳을 바라보면 안되기 때문에 끝내줘야함.
                if(left == right) break;

                if(number[left] + number[right] > choice){
                    right--;
                }else if(number[left] + number[right] < choice){
                    left++;
                }else {
                    res+=1;
                    break;
                }

            }
        }
        System.out.println(res);

    }
}