[BOJ_2295] 세 수의 합

https://www.acmicpc.net/problem/2295

2295번: 세 수의 합

자연수로 이루어진 집합에서 세 수 a, b, c, d를 뽑았을 때, a+b+c=d를 만족하는 최대 d를 구하는 문제입니다.
모든 경우의 수를 따져서 풀 수 있는데, 이럴 경우 N이 최대 1,000이기 때문에 N^3은 1,000,000,000으로 시간초과가 될 것입니다.

💎 풀이

a+b+c=d 우리가 성립시켜야 할 식입니다.
이 식을 이항해보면 a+b = d-c 를 만들 수 있습니다.

1. 모든 a+b를 Set에 저장할 것입니다. (N^2)
2. a+b를 저장한 Set에서 d-c가 포함되어 있는지 검사합니다.
3. 포함된 경우 해당 d를 Set에 저장합니다.
4. d가 저장된 Set에서 가장 큰 수를 찾으면 정답입니다. ^^

 

💎 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class BOJ_2295 {

    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        HashSet<Integer> set = new HashSet<>();
        for(int i=0; i<N; i++) {
            set.add(Integer.parseInt(br.readLine()));
        }
        HashSet<Integer> abSum = getABSum(set);
        HashSet<Integer> dSet = getDSet(set, abSum);

        int result = 0;
        for(int d : dSet) {
            result = Math.max(result, d);
        }

        System.out.println(result);
    }

    public static HashSet<Integer> getABSum(HashSet<Integer> set) {
        // a+b 모든 경우의 수
        HashSet<Integer> ret = new HashSet<>();

        for(int a : set) {
            for(int b : set) {
                ret.add(a + b);
            }
        }

        return ret;
    }

    public static HashSet<Integer> getDSet(HashSet<Integer> set, HashSet<Integer> abSum) {
        // d-c == a+b 인 모든 d를 저장
        HashSet<Integer> dSet = new HashSet<>();

        for(int d : set) {
            for(int c : set) {
                if(abSum.contains(d-c)) {
                    dSet.add(d);
                }
            }
        }

        return dSet;
    }
}