BOJ 2295 - 세 수의 합

2295번: 세 수의 합

 

N(5 ≤ N ≤ 1,000) 개의 자연수로 이루어진 집합 U.

U에서 적당히 3개의 수를 뽑았을 때 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다.

이때 가장 큰 d를 찾아라

집합의 크기는 최대 1000이다. 집합이니 중복은 존재하지 않는다.

1000개에서 3개를 뽑고 전부 확인하면 시간초과가 발생할 것이다.

또한 집합 U의 원소는 2억보다 작거나 같은 자연수이다. 세 수를 더한 경우에도 정수 범위 내로 처리 가능하다.

두 수의 합으로 만들 수 있는 숫자들을 미리 기록해 놓고 빠르게 찾을 수 있으면 해결할 수 있다.

1. 두 수의 조합으로 만들 수 있는 합을 Set으로 관리
2. 입력받은 집합을 오름차순으로 정렬하고 뒤에서부터 확인
3. 현재 정답 후보와 후보 앞에 있는 숫자들을 빼가며 해당 값이 두 수의 합 Set에 존재하는지 확인

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

    static FastReader scan = new FastReader();
    static int N;
    static List<Integer> nums;

    static void input() {
        N = scan.nextInt();
        nums = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            nums.add(scan.nextInt());
        }

        Collections.sort(nums);
    }

    static void solve() {
        Set<Integer> twoSum = new HashSet<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                twoSum.add(nums.get(i) + nums.get(j));
            }
        }

        for (int i = nums.size() - 1; i > 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                int cand = nums.get(i) - nums.get(j);
                if (twoSum.contains(cand)) {
                    System.out.println(nums.get(i));
                    return;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}