[Java] 백준(골드-4) 2295번 - 세 수의 합

문제 풀이

---

이번 문제를 해결하기 위해서는 이분 탐색을 이용하는 것도 중요하지만, 문제를 단순화하여 접급하는 것이 키 포인트이다.

아이디어 도출

세수의 합인 x+y+z를 일일이 구하는 것도 좋겠지만 이 식을 단순화하여 접근하면 더욱 쉬울 수 있다.

x+y+z=k -> x+y=k-z

x+y+z=k 라는 식은 x+y=k-z 식과도 같다는 것은 누구나 알 수 있다. 이렇게 식을 쉽게 바꾸면 아래와 같이 접근할 수 있다.

1. x와y의 합이 되는 모든 경우를 찾아 배열 등에 저장한다.
2. k-z를 만족하는 수를 위 x+y의 합 배열에서 찾는다.
3. k-z를 만족하는 수가 있다면 가장 큰 k가 문제에서 요구하는 답이 된다.

유의할 점은 k-z를 만족하는 수를 탐색할 때, 시간초과를 고려하여 이분탐색을 이용해야 한다.

결국, 이분탐색도 중요하지만 문제 해결을 위한 새로운 식을 도출한 것처럼 문제를 바라보는 시선과 안목도 중요하다!

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] U = new int[N];

        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(br.readLine());
            U[i] = num;
        }
        Arrays.sort(U);

        List<Integer> two_sum_list = new ArrayList<>();
        for(int i=0; i<N; i++) {
            for(int j=i; j<N; j++) {
                two_sum_list.add(U[i] + U[j]);
            }
        }
        Collections.sort(two_sum_list);

        int answer = 0;
        for(int i=U.length-1; i>=0; i--) {
            for(int j=i; j>=0; j--) {
                int kz = U[i] - U[j];
                // 맨 뒤부터 두수의 차(k-z)이 모든 두수의 합(x+y)에 속해있다면 x+y+z=k를 달성하는 것과 동일함.
                // 이때, x+y의 합이 담긴 List에 k-z값의 존재여부를 이분탐색으로 탐색한다.
                if(binarySearch(two_sum_list, kz)) {
                    answer = U[i];
                    bw.write(answer+"\n");
                    bw.close();
                    br.close();
                    return;
                } 

            }
        }   
    }

    static boolean binarySearch(List<Integer> list, int n) {
        int left = 0;
        int right = list.size() - 1;
        int mid;

        while (left <= right) {
            mid = (left + right) / 2;
            if (list.get(mid) < n) left = mid + 1;
            else if (list.get(mid) > n) right = mid - 1;
            else return true;
        }
        return false;
    }
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.