문제링크

풀이

처음에는 x,y,z의 조합을 전부 구해서 합을 구한 후에, u 배열에서 이분탐색을 통해 값을 찾으려고 했다. 하지만 그렇게 풀이하게 되면 N이 $1000^3$이 되며 시간초과가 나버린다.

다른 풀이를 생각해보려했지만 도저히 생각이 안나서..
찾아본 결과,

문제의 출력 부분에서 힌트를 얻을 수 있었다.
x+y+z=k 라는 수식에서 x+y=k-z라는 식을 얻을 수 있고, 이렇게 되면 두 수의 합 또는 차의 조합만 구하면 되기 때문에 이중 for문으로 풀이할 수 있게 된다.

코드

package BOJ;

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

public class sol2295 {
    static int n;
    static int[] u;
    static int[] sum;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        u = new int[n];

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

        sum = new int[n * n];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum[idx++] = u[i] + u[j];
            }
        }

        Arrays.sort(sum);

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int target = u[i] - u[j];
                if (Arrays.binarySearch(sum, target) > -1) {
                    max = Math.max(max, u[i]);
                }
            }
        }
        System.out.println(max);
    }
}

문제를 풀며..

사실 구현 자체는 굉장히 간단했지만..
저 수식을 생각해내는 것이 이 문제가 골드인 이유인 거 같다.
이런 것도 문제를 풀다보면 늘어야할텐데.