[백준] 1253 좋다

---

 이분탐색을 통해 해결할 수 있다. 유의해야할 점은 이분탐색은 배열이 정렬되어있는 상태여야 하는 것, 그리고 배열의 수가 자연수라고 정의되어 있지 않기 때문에 0이 포함되는 경우를 생각해야된다.

 

0이 포함되는 경우 자기 자신을 더하는 경우가 발생할 수 있기 때문에 타겟이 되는 수를 제외한 배열에서 이분 탐색을 수행해야한다.

 

Python

 

	from sys import stdin
	readline = stdin.readline
	N = int(readline())
	arr = list(map(int, readline().split()))
	def solve():
	cnt = 0
	arr.sort()
	for i in range(len(arr)):
	if binary_search(i, arr[i]):
	cnt += 1
	print(cnt)
	def binary_search(i, target):
	temp = arr[:i] + arr[i+1:]
	left = 0
	right = N - 2
	while left < right:
	cur = temp[left] + temp[right]
	if cur > target:
	right -= 1
	elif cur < target:
	left += 1
	else:
	return True
	return False
	solve()

view raw BOJ1253.py hosted with ❤ by GitHub

Java

 

	import java.io.*;
	import java.util.*;
	public class BOJ1253 {
	static int N;
	static int[] arr;
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	N = Integer.parseInt(br.readLine());
	arr = new int[N];
	StringTokenizer st = new StringTokenizer(br.readLine());
	for(int i=0;i<N;i++){
	arr[i] = Integer.parseInt(st.nextToken());
	}
	Arrays.sort(arr);
	solve();
	}
	public static void solve(){
	int res = 0;
	for(int i=0;i<N;i++){
	int[] arrSplit = splitArray(i);
	if(binarySearch(arr[i], arrSplit)){
	res++;
	}
	}
	System.out.println(res);
	}
	public static boolean binarySearch(int target, int[] arrSplit){
	int left = 0; int right = N-2;
	while(left < right){
	int cur = arrSplit[left] + arrSplit[right];
	if(cur > target){
	right--;
	} else if(cur < target){
	left++;
	} else {
	return true;
	}
	}
	return false;
	}
	public static int[] splitArray(int idx){
	int[] temp = new int[N-1];
	int i = 0;
	for(int j=0;j<N;j++){
	if(j==idx) continue;
	temp[i] = arr[j];
	i++;
	}
	return temp;
	}
	}

view raw BOJ1253.java hosted with ❤ by GitHub