BOJ_2295_세 수의 합 (Java)

[Gold IV] 세 수의 합 - 2295

문제 링크

성능 요약

메모리: 16932 KB, 시간: 196 ms

분류

이분 탐색, 자료 구조, 해시를 사용한 집합과 맵, 중간에서 만나기

제출 일자

2025년 1월 31일 23:53:19

문제 설명

N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.

예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다.

입력

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된다. U의 원소는 200,000,000보다 작거나 같은 자연수이다. 답이 항상 존재하는 경우만 입력으로 주어진다.

출력

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최대가 되도록 하는 것이 목적이다. x, y, z, k가 서로 같아도 된다. 이때, k번째 수를 출력하면 된다.

문제 풀이

첫 풀이는 세 수의 합을 O(N^3)으로 구현하지 않고 a+b+c=k일 때 a+b를 O(N^2)로 구해놓고 k-c도 O(N^2)로 구해 풀었다.

하지만 이를 더 보완하여

k-a-b를 만족하는 c를 이분탐색으로 찾아보았다.

이분탐색 코드가 훨씬 효율적이었다. 시간 복잡도는 O(N³ log N) 로 늘었다고 생각했는데 HashSet의 오버헤드가 더 큰건가 생각했다.

두가지 코드 모두 첨부하겠다.

코드

Java a+b와 K-c로 찾기

package BOJ_2295_세수의합;
        
/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, arr[];
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2295_세수의합/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        HashSet<Integer> set = new HashSet<>();

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

//        System.out.println(set);

        int res = 0;
        for(int k=N-1; k>=0; k--){
            for(int i=0; i<N; i++){
                if(set.contains(arr[k]-arr[i])){
                    res = Math.max(res, arr[k]);
                }
            }
        }
        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
        br.close();
    }
}

---

이분탐색 사용 코드

package BOJ_2295_세수의합;

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main2 {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, arr[];
    public static void main(String[] args) throws Exception {
        new Main2().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2295_세수의합/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int left, right, res=0;
        for(int i = N-1; i >= 0; i--){
            for(int j=i-1; j>=0; j--){
                for(int k=0; k<=j; k++){
                    if(arr[i]-(arr[j]+arr[k]) <= 0) break;
                    left = 0;
                    right = k;
                    while(left <= right){
                        int mid = left + (right - left)/2;
                        if(arr[mid] >= arr[i]-(arr[j]+arr[k])){
                            right = mid - 1;
                            res = mid;
                        }
                        else{
                            left = mid + 1;
                        }
                    }

                    if(arr[res] == arr[i]-(arr[j]+arr[k])){
                        System.out.println(arr[i]);
                        return;
                    }
                }
            }
        }



        bw.flush();
        bw.close();
        br.close();
    }
}