[백준 / 골드4] 1253 좋다 (Java)

문제 보기

사용한 것

• 어떠한 숫자를 두 수의 덧셈으로 구할 수 있는지 판별할 때 하나의 수를 고정으로 놓고 더할 숫자를 탐색하기 위한 이분 탐색

풀이 방법

• 이분 탐색을 사용하기 위하여 정렬한다.
• 어떠한 수를 두 수의 합으로 구할 수 있는지 판별한다.
  • 하나의 수를 배열에서 고른다.
  • 나머지 두 번째 수를 이분 탐색으로 구한다.

코드

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[] arr = Stream.of(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();

        Arrays.sort(arr);

        int answer = 0;
        for (int i = n - 1; i >= 0; i--) {
            int num = arr[i];
            boolean isGoodNum = false;
            for (int j = n - 1; j >= 0; j--) {
                int key = num - arr[j];
                int l = 0;
                int r = j - 1;
                if (j == i) {
                    continue;
                }
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (arr[mid] > key) {
                        r = mid - 1;
                    } else if (arr[mid] == key && mid != i && mid != j) {
                        isGoodNum = true;
                        break;
                    } else {
                        l = mid + 1;
                    }
                }

            }
            if (isGoodNum) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}