[JAVA][백준 2295] 세 수의 합

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

---

풀이 과정

이분탐색을 연습하느라 해당 문제는 이분탐색으로 푸는 것을 알고선 시작..!

문제를 읽어보면 집합안에 있는 숫자를 이용해서 집합 안에있는 또 다른 숫자를 만드는데

그 중 제일 큰 값을 구하는 문제이다.

그리고 중복도 된다.

 

A+B+C=X가 되는 값을 구하면 되는데

무작정 for문으로 돌면 답은 나오지만 문제 조건이 N이 1000개까지 나올 수 있어서

연산량은 1000^3 = 1000,000,000 정도가 나오기 때문에 시간제한에 걸린다.

그래서 다른 방법을 사용해야하는데

A+B = X - C를 이용하는 방법이다.

 

일단 2중 for문을 돌면서 A+B로 나올 수 있는 모든 수를 Set에 저장한 후

또 2중for문을 돌아서 X-C를 구한 다음 Set에 해당 숫자가 있는지 확인하면

2N^2이 된다.

 

딱히 이분 탐색은 안써도 되는 것 같은데..
일단 위의 방법대로 코드를 짜봐야겠다.

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

public class G_2295 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                set.add(arr[i] + arr[j]);
            }
        }

        int max = -1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int num = arr[i] - arr[j];
                if (set.contains(num)) max = Math.max(max, arr[i]);
            }
        }

        System.out.println(max);
    }
}

채점 결과는 통과.

딱히 이분탐색은 사용하지 않아도 되나보다.

 

통과는 했지만 이분탐색을 연습해보기 위해 이분탐색으로 풀어야겠다.

 

A+B값을 Set에 넣었던 부분을 Set에 넣지말고 배열에 넣은다음 정렬을 해야되는데

배열의 길이를 어떻게 할지 계산해야한다.

for문의 인덱스 부분을 보면 첫번째 for문이 0부터 N까지, 두번째 for문이 첫번째 for문의 인덱스부터 N까지 돈다.

이유는

둘다 0부터 0까지 하면

1+2와 2+1이 같이 저장되는데 얘는 결국 3으로 중복값이라서 연산을 할 필요가 없다.

따라서 결국

(N) + (N - 1) + ... + 1 이기때문에 배열의 크기는 N(N + 1)/2가 된다.

 

채점 결과는 성공~~

확실히 Set을 사용하는 것보단 오래걸린다.

---

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class G_2295 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int[] sums = new int[N * (N + 1) / 2];
        int idx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                sums[idx++] = arr[i] + arr[j];
            }
        }
        Arrays.sort(sums);

        int max = -1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int num = arr[i] - arr[j];
                if (binarySearch(sums, num)) max = Math.max(max, arr[i]);
            }
        }

        System.out.println(max);
    }

    private static boolean binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return true;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}

---

 

이 문제는 이분탐색을 연습한다기보단 수학을 연습한 느낌이다..

이분 탐색은 그냥 기본 이분 탐색이고 그냥 수를 찾는데 사용한 것 밖에 없어서 그냥 자바에 구현되어있는 이분탐색을 사용해도 된다.

처음 A와B,C 를 어떻게 결정할지 고민하는 부분이 가장 힘들었던 것 같다.

풀이에서는 술술 이미 다 알고 있는것처럼 적었지만 사실 엄청 많이 고민했던 문제이다
X를 결정한다음 3개를 정하는 방법을 처음 생각했다가..
A+B만 결정하고 나머지 하나를 결정하는 방법을 생각했다가...(결국 위의 방법과 다르지 않음)

마지막에 A+B를 결정하고 X-C를 결정한다음 비교하는 방법을 생각해낸 것..

이런 문제는 너무 어렵다...

 

그래도 계속 코테 경험을 늘리다보면 다양한 방법을 많이 접하고 나중엔 고민도 안하고 푸는 날이 오겠지?