링크

2295 세 수의 합

문제

풀이

이 문제는 이분탐색까진 했는데 3중 for문으로 풀었다. 당연히 O(n3)으로 시간초과가 났다.(n은 1000개 시간제한은 1초)
그래서 풀이를 봤다.
풀이는 A+B+C=K니까 A+B = K-C를 이용해서 문제를 풀이하는 것이다. (사람들 되게 똑똑하다)

1. A+B를 2중 for문을 통해 합을 list에 넣어준다.
2. 다시 2중 for문을 통해 K-C를 만들고 이분탐색을 통해서 K-C가 A+B를 담은 list에 있는지 체크하고 있으면 max값을 갱신하면 된다.

코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.*;
import java.util.List;

public class Main{
    public static int max = 0;
    public static List<Integer> sumArr = new ArrayList<>();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        //a + b + c = k 이거는 a + b = k - c로 풀자
        //a+b 만들기
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                sumArr.add(arr[i] + arr[j]);
            }
        }

        Collections.sort(sumArr);

        //k-c를 넣어서 이분탐색해서 a+b가 있나 없나 체크하면 된다.
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(binarySearch(arr[i] - arr[j])){
                    max = Math.max(max, arr[i]);
                }
            }
        }

        System.out.println(max);


    }

    public static boolean binarySearch(int target){
        if(target <= 0) return false;

        int start = 0;
        int end = sumArr.size() - 1;

        while(start <= end){
            int mid = (start + end) / 2;

            if(target == sumArr.get(mid)){
                max = Math.max(max, target);
//                System.out.println("찾음 max = " + arr[mid]);
                return true;
            }

            if(target > sumArr.get(mid)){
                start = mid + 1;
            } else {
                end = mid - 1;
            }



        }

        return false;
    }

}