[BOJ 1253] 좋다(G4)

 

📍 문제 

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

 

📍 문제 풀이 

 

두 개를 더해서 어떤 수가 나오려면 정렬해서 이분 탐색을 통해 찾아내자

 

기본적인 이분 탐색의 경우에는 아래의 경우만 확인해주면 되지만

우리는 두 개를 더해서 구하려는 어떤수 가 지정된 하나의 값이 아니라

몇 개인지를 구하려는 것이기 때문에 for문을 돌려줘야한다.

int sum = nums[start] + nums[end];
if (sum == nums[i]) {
	result++;
	break;
} else if (sum < nums[i]) {
	start++;
} else {
	end--;
}

 

그리고 지정한 `start`와 `end` 값이 for문의 인덱스와 같다면

어떤 수를 더해도 `nums[i]`보다 커지기 때문에 조건문으로 처리해줘야한다.

if (start == i) {
	start++;
} else if (end == i) {
	end--;
}

 

📍 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] nums = new int[n];
		for (int i = 0; i < n; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(nums);

		int result = 0;
		for (int i = 0; i < n; i++) {
			int start = 0;
			int end = n - 1;

			while (start < end) {
				if (start == i) {
					start++;
				} else if (end == i) {
					end--;
				}else{
					int sum = nums[start] + nums[end];
					if (sum == nums[i]) {
						result++;
						break;
					} else if (sum < nums[i]) {
						start++;
					} else {
						end--;
					}
				}
			}
		}
		System.out.println(result);
	}
}