백준 1253 좋다 C/C++

좋다 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

17000

4197

3022

23.844%

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

예제 입력 1 복사

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1 복사

8

#include <iostream>


using namespace std;

void MergeTwoArea(int arr[], int left, int mid, int right);
void MergeSort(int arr[], int left, int right);



int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n,pos1,pos2,k,cnt=0;
	cin >> n;
	int* arr = new int[n];

	
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	MergeSort(arr, 0, n - 1);

	for (int i = 0; i < n; i++)
	{
		pos1 = 0;
		pos2 = n - 1;
		k = arr[i];
		while (pos1 < pos2)
		{
			
			if (arr[pos1] + arr[pos2] == k)
			{
				if (pos1 != i && pos2 != i)
				{
					cnt++;
					break;
				}
				else if (i == pos1)
					pos1++;
				else if(i= pos2)
					pos2--;
			}
			else if (arr[pos1] + arr[pos2] < k)
				pos1++;
			else
				pos2--;

		}
	}
	printf("%d", cnt);

	return 0;
}

void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	if (fIdx > mid)
	{
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

void MergeSort(int arr[], int left, int right)
{
	int mid;

	if (left < right)
	{
		// 중간 지점을 계산한다.
		mid = (left + right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);

		// 정렬된 두 배열을 병합한다.
		MergeTwoArea(arr, left, mid, right);
	}
}

 

우선 배열을 정렬하면 풀기가 더 쉽다.

그렇기에 시간이 nlog n이 걸리는 병합정렬을 통해 정렬을 한다.

 

 

예제입력을 보자.

1

1 2 3 4 5 6 7 8 9 10

 

 

위와 같이 배열에 값이 입력돼있고, 2개의 포인터를 사용하여 합을 나타낸다

 

pos1이 가리키는 값과 pos2가 가르키는 값이 i가 되는지를 확인하는 것이다.

i는 1부터 10까지 움직이면서, 그 값이 pos1+pos2와 같은지 확인한다.

 

i가 1인 경우는 어떤 값도 나올 수 없다.

i가 2인 경우도 마찬가지이다.

 

i가 3인 경우를 보자.

pos1은 1을 가리키고, pos2는 10을 가리킨다.

pos1+pos2가 각각 가리키는 값의 합이 i가 가리키는 값보다 크다.

그렇다면 pos2를 왼쪽으로 댕겨와야 한다.

 

이번에는 11 -> 10으로 가져왔다

하지만 여전히 크기 때문에 계속 줄이다보면 2가 되면, 이는 3과 일치한다.

이때 cnt++를 해준다.

 

하지만 이렇게 계속 줄여도 값이 없을 경우에는 i를 오른쪽으로 이동시킨다.

이 과정을 반복해서 갯수를 출력한다.

 

요약하면

arr[pos1] + arr[pos2] > arr[i] : pos2--;

arr[pos1] + arr[pos2] < arr[i] : pos1++;

arr[pos1] + arr[pos2] ==arr[i] : cnt++; break;