BOJ - 2295 세 수의 합

leehyunjon·2022년 5월 27일

boj 이분 탐색

Algorithm

목록 보기

49/162

2295 세 수의 합 : https://www.acmicpc.net/problem/2295

Problem

Solve

세 수의 합이 집합 U에 있는 경우 합의 최댓값을 구하는 문제.
세 수를 구하고 O(N^3) 합의 포함 여부를 구하면 O(N) 시간 초과가 발생한다.
적어도 O(N^2)이나 O(N^2*logN)을 사용해야한다.

N^2은 두개의 좌표를 구하는 방법, logN은 두 좌표의 합을 찾는 방법으로 해결 할 수 있다.

두개의 좌표는 x,y를 구하는 방법을 집합 U에서 두 좌표를 합한 결과를 미리 만들어 놓아 찾고 U[k]+U[z]의 값을 이분 탐색으로 찾아내는 것이다.
즉, U[x]+U[y]+U[z] = U[k]를 U[x]+U[y] = U[k]-U[z]로 변형해서
k와 z를 찾고 O(N^2) 두 좌표 합 배열에서 이분탐색 O(logN)으로 찾을수 있다.

참고로 답이 항상 존재한다는 조건이 있었기 때문에 이분탐색으로 찾을수 있다.

Code

public class 세수의합 {
	static int N;
	static int[] U;
	static int[] two;
	static int answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		//집합 U크기
		N = Integer.parseInt(br.readLine());
        //자연수 집합
		U = new int[N];
		for(int i=0;i<N;i++){
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			U[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(U);
        //두 자연수의 합으로 two 배열 초기화
		makeTwo();

		answer = 0;

		//k값과 l값 찾기
		for(int k=0;k<N;k++){
			for(int l=0;l<N && l<=k;l++){
				int result = binarySearch(U[k]-U[l]);
                //k와 l의 차이 값이 two배열에 존재한다면 k값의 최댓값을 갱신해준다.
				if(result != -1){
					answer = Math.max(answer, U[k]);
				}
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static void makeTwo(){
		HashSet<Integer> set = new HashSet<>();

		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				set.add(U[i]+U[j]);
			}
		}

		two = new int[set.size()];

		int idx=0;
		for(int num : set){
			two[idx++] = num;
		}
		Arrays.sort(two);
	}

	static int binarySearch(int target){
		int start=0;
		int end=two.length-1;

		while(start<=end){
			int mid = (start+end)/2;

			if(two[mid]>target){
				end = mid-1;
			}else if(two[mid]<target){
				start = mid+1;
			}else{
				return mid;
			}
		}
		return -1;
	}
}