[백준] 2295 세 수의 합

문제 링크 : https://www.acmicpc.net/problem/2295

🍊해결방법

• 세수의 합을 구하고 나서 그 합을 이진탐색으로 찾으려고 하면 N^3 을 시간초과
• 두수의 합을 미리 구하자
• sum + arr[i] = arr[j] 이 조건을 만족하면 됨
• sum = arr[j] - arr[i] 이중 for문을 사용해서 조건을 구하고 sum을 이진탐색 돌면서 확인하자
• N^2으로 해결

😀풀이

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

public class Main {

    static int N;
    static int[] arr;
    static int max;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 주어진 수 중에서 한번을 3번 뽑을 수 있다
        // 3개의 합이 해당 수가 있는지 없는지 이분탐색을 활용해서 찾자
        // N^3이라 시초
        // 두개의 합을 미리 구하고 그 합과 arr[i] 더한 것과 arr[j]를 찾으면 됨 이러면 N^2

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

        arr = new int[N];

        List<Integer> list = new ArrayList<>();

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

        for(int i=0; i<N; i++){
            for(int j=i; j<N; j++){
                list.add(arr[i] + arr[j]);
            }
        }

        // list[i] + arr[i] = arr[j]
        Collections.sort(list);

        int ans = 0;

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){

                if(arr[j] - arr[i] < 0) continue;

                // 두수합을 이진탐색으로 찾자
                int s = 0;
                int e = list.size()-1;

                int target = arr[j] - arr[i];

                while(s <= e){

                    int mid = (s+e)/2;

                    int num = list.get(mid);

                    if (num > target){
                        e = mid - 1;
                    }
                    else if (num < target){
                        s = mid + 1;
                    }
                    else{
                        ans = Math.max(ans, num + arr[i]);
                        break;
                    }
                }

            }
        }


        System.out.println(ans);



    }



}