2295번 세 수의 합 ( JAVA )

문제:

• 문제 링크

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번째 수를 출력하면 된다.

접근 방법

처음 접근 방식은 백트래킹을 통한 순열을 찾고 이분탐색을 통해 값이 있는지 확인하는 거 였는데 시간초과가 발생했다.

그래서 생각해낸게 중복때문일 것같아서 중복을 제거하는 자료 구조 인 Set을 사용해서 데이터를 저장하고 계산했지만 이 방식또한 시간초과가 발생했다.

그러면 알고리즘이 문제인것같아서 생각을 다시 해보았는데 우선 Set을 사용하여 첫번째 수와 두번째 수를 더 해놓고 합과 세번째 수를 뺀 것과 같으면 합이 정답이 된다는 것을 깨달았다.

1. 두 수의 합을 중복을 제외하고 저장
2. 두 수의 차를 구하고 차가 합에 있으면 두 수 중 큰 값이 정답
   예) 1+2 , 6 - 3 이렇게 결과 값이 나오면 6이 정답이 되는 구조

코드

접기/펼치기

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class 세_수의_합 {

    static int N;
    static long[] arrays;
    static long result = 0;

    public static void findSum() {
        Arrays.sort(arrays);

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

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


        for (int k = N - 1; k >= 0; k--) {
            for (int i = 0; i < N; i++) {
                long diff = arrays[k] - arrays[i];
                if (set.contains(diff)) {
                    result = arrays[k];
                    return;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        arrays = new long[N];
        for (int i = 0; i < N; i++) {
            arrays[i] = sc.nextInt();
        }

        findSum();
        System.out.println(result);
    }
}

생각보다 어려웠다. 실력이 많이 부족한것같다.