2295 - 세 수의 합 (Java)

 

---

 

문제

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

 

풀이

알고보면 참 단순한 문제다.

 

우리는 x + y + z = k 라는 공식을 활용해서 답을 찾아야 하는데,

 

이 표현은 x + y = k - z 로도 나타낼 수 있다는 점을 알아야 한다.

 

x + y + z 의 경우의 수를 모두 구할려면 O(N^3) 이 걸릴 테지만 

 

이를 조금 비틀어  x + y = k - z  를 활용하면 양쪽의 식들 값을 구하기 위해서 O(N^2) 의 시간에 풀이할 수 있다.

 

x + y 의 값들을 set 에 저장한다음, k - z 값이 set에 있는지 확인하면 된다.

 

이 때 k 값이 가장 큰 값을 찾고 있기 때문에 배열을 오름차순으로 정렬해준다음,가장 뒤에서부터 k 값을 세팅해서 탐색을 시작하면 된다.

 

k 값을 큰 값부터 탐색하기 때문에 set 에 존재하는 값이 나올 때, 그게 가장 큰 값이기 때문에 바로 출력해주면 된다.

 

※ 참고로 이분탐색 방법은 k - z 를 찾는 과정을 O(N) 에서 O(logN) 으로 줄임으로써 풀이가 가능한 것이다.

 

코드

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

public class Main {

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        ArrayList<Long> numbers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            numbers.add(Long.parseLong(br.readLine()));
        }
        Collections.sort(numbers);

        Set<Long> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                set.add(numbers.get(i) + numbers.get(j));
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                if(set.contains(numbers.get(i) - numbers.get(j))){
                    System.out.println(numbers.get(i));
                    return;
                }
            }
        }

    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기

 

감이 안와 검색을 좀 하고 풀었는데

 

x + y + z = k  -> x + y = k - z 로 어떻게 생각할 수 있을까.. 신기하다