[알고리즘] C++ 백준 1253 좋다

백준 1253

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

1253번: 좋다

풀이 전 나의 생각

N개의 수에서 어떤 수가 다룬 수 두 개의 합으로 나타낼 수 있다면 "좋다" 라고 한다.

따라서 "좋다"를 만족하는 좋은 수가 몇 개인지 구해야한다.

 

조건

N(1 ≤ N ≤ 2,000)

|Ai| ≤ 1,000,000,000, Ai는 정수

 

Solution

조건으로 알 수 있는 것은 일반적인 탐색 방법인 3중 for문을 이용한 방법은

2000 * 2000 * 2000의 계산 횟수로 시간 제한을 지키지 못한다.

-> 이분 탐색을 이용한 풀이가 필요하다.

 

Ai는 정수면서 절대값이기 때문에 범위는 10억이다. -> 데이터 타입은 int형으로 설정

 

1. N의 어떤 수를 만들기 위해 이분탐색을 진행한다.

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

		while (start < end)
		{
			...

 

 

2. 중복을 피하기 위해 N의 어떤 수는 포함하지 않는다.

if (start == i)
{
	start++;
	continue;
}

if (end == i)
{
	end--;
	continue;
}

주어진 N개의 수 배열의 시작과 끝을 합하며 어떤 수 N을 만들 수 있는지 검사하려고한다.

이 과정에서 어떤 수 N을 만들기 위해 어떤 수N을 포함하여 합을 구한다면 중복을 허용하지 않은 문제의 조건을

만족하지 못하게된다.

 

 

3. 시작과 끝의 합이 어떤 수 N과 같다면 최종값을 증가시켜준다.

if (num_arr[i] == num_arr[start] + num_arr[end])
{
	ans++;
	break;
}

 

 

4. 시작과 끝의 합이 어떤 수 N과 다르다면 시작과 끝을 조정해준다.

if (num_arr[i] > num_arr[start] + num_arr[end])
{
	start++;
}
else
{
	end--;
}

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int num_arr[2001];

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

	int N, ans = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> num_arr[i];
	}

	sort(num_arr, num_arr + N);

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

		while (start < end)
		{
			if (start == i)
			{
				start++;
				continue;
			}

			if (end == i)
			{
				end--;
				continue;
			}

			if (num_arr[i] == num_arr[start] + num_arr[end])
			{
				ans++;
				break;
			}

			if (num_arr[i] > num_arr[start] + num_arr[end])
			{
				start++;
			}
			else
			{
				end--;
			}
		}
	}

	cout << ans;
}