[백준/C & C++] 3273 두 수의 합

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

3273번: 두 수의 합

C

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b);
int binarySearch(int arr[], int n, int find);

int main()
{
	int n, result, count=0;
	scanf("%d", &n);

	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
	qsort(arr, n, sizeof(int), compare);
	scanf("%d", &result);

	for (int i = 0; i < n; i++)
	{
		int find = result - arr[i];
		if (binarySearch(arr, n, find) != -1) count++;
	}

	printf("%d", count/2);
	return 0;
}

int compare(const void* a, const void* b)
{
	int n1 = *(int*)a;
	int n2 = *(int*)b;

	if (n1 < n2) return -1;
	else if (n1 > n2) return 1;
	else return 0;
}

int binarySearch(int arr[], int n, int find)
{
	int low = 0, high=n-1, mid;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (find == arr[mid]) return mid;
		else if (find < arr[mid]) high = mid - 1;
		else if (find > arr[mid]) low = mid + 1;
	}
	return -1;
}

C++

#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;

int binarySearch(int n, int find, int arr[]);

int main()
{
	int n, result, count=0;
	cin >> n;
	int* arr = new int[n];
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);
	cin >> result;

	for (int i = 0; i < n; i++)
	{
		int find = result - arr[i];
		if (binarySearch(n, find, arr) != -1) count++;
	}

	cout << count / 2;
	delete []arr;
	return 0;
}

int binarySearch(int n, int find, int arr[])
{
	int low = 0, high = n - 1, mid;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (find == arr[mid]) return mid;
		else if (find < arr[mid]) high = mid - 1;
		else if (find > arr[mid]) low = mid + 1;
	}
	return -1;
}

코드 설명

값들을 입력받고 정렬한 뒤에 result-arr[i]의 값이 배열에 있는지 이진탐색을 이용해 찾고, 값이 있다면 count를 증가시킨다. a+b=result일 경우, a를 찾는 경우와 b를 찾는 경우가 각각 수행되는데, 이는 같은 경우이므로 나누기 2를 한 count/2를 출력한다. 

n을 입력받고 동적배열을 만든다. 배열에 값들을 입력받고 정렬한다. (c의 경우에는 qsort사용, c++은 algorithm 헤더 파일 내 sort함수 이용) 이후 x를 입력받고, 반복문을 이용해서 x-arr[i]가 배열에 있는지를 이진탐색을 이용해서 찾는다. 반환값이 -1이 아닐 경우 배열에 찾는 값이 있다는 뜻이므로 count를 증가시킨다.

 

x = arr[p] +arr[q]를 만족한다면 반복문에서 i=p일 때, i=q일 때가 각각 세어지므로 나누기 2한 값을 출력하고 프로그램을 종료한다. 

 

느낀 점

처음에 정렬하지 않고 그때그때 값을 찾는 방식을 사용했다가 시간초과가 되었다. 코드를 수정해서 정렬하고, 이진탐색을 사용하는 방법으로 문제를 푸니 바로 통과했다.