카테고리: 이분탐색, 완전탐색

문제

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

풀이 방식

x + y + z = k 인 수를 찾는 것이므로 x,y,z를 조사하기 위해 3중 for문을 쓰면 시간초과가 납니다. 따라서 x + y = k - z로 식을 변형하여 x+y의 집합 배열을 만들고 그 배열 안에 k - z인 수를 찾습니다. 그 중 최대값이 정답이 됩니다. 이제 2중 for문으로 문제를 풀 수 있습니다.

여기서 두가지의 풀이방식을 사용할 수 있습니다.

• Set을 이용한 풀이
• 이분 탐색을 이용한 풀이

최종 코드

Set을 이용한 풀이입니다.

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


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

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

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

        // 두개의 합 배열 만들기
       Set<Integer> set = new HashSet<>();
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){// 중복을 최소화 하기 위해 j=i부터
                set.add(u[i] + u[j]);
            }
        }

        int max = -1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int target = u[i] - u[j];// k는 u[i]이다.
                if(set.contains(target)){
                    max = Math.max(max, u[i]);
                }
            }
        }

        System.out.println(max);

    }
}

이분 탐색을 이용한 풀이입니다.

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


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

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

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

        // 두개의 합 배열 만들기
        int[] sum = new int[n * (n+1) / 2];
        int index = 0;
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                sum[index++] = u[i] + u[j];
            }
        }

        Arrays.sort(sum);

        int max = -1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int target = u[i] - u[j];// k는 u[i]이다.
                if(Arrays.binarySearch(sum, target) > -1){
                    max = Math.max(max, u[i]);
                }
            }
        }

        System.out.println(max);

    }
}