[C/C++] 백준 1253번 - 좋다

 

백준 1253번 좋다

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

1253번: 좋다

     ●  N이 최대 2000이므로 시간 복잡도는 최소 O(nlogn)이 되어야 하므로 투 포인터 알고리즘 사용하기 

     ● 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함시키면 안 됨

     ● 수를 입력받아 배열에 입력받은 후 정렬

     ● 투 포인터 i,j를 배열 A 양끝에 위치시키고 적합한 투 포인터 이동원칙을 활용, 판정이 되는 수를 K라고 지정

     ● 투 포인터 이동 원칙

         A[i] + A[j] < K : i++;

         A[i] + A[j] == K : count++(i!=K&&j!=K일 때); break;

         A[i] + A[j] > K : j--

 

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	vector<int>A(N, 0);

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	
	sort(A.begin(), A.end());
	int result = 0;

	for (int k = 0; k < N; k++) {
		long find = A[k];
		int i = 0;
		int j = N - 1;

		while (i < j) {
			
			if (A[i] + A[j] == find) {
				
				if (i != k && j != k) {
					result++;
					break;
				}
				
				else if (i == k) {
					i++;
				}
				
				else if (j == k) {
					j--;
				}

			}
			
			else if (A[i] + A[j] < find) {
				i++;
			}
			
			else {
				j--;
			}
		}
	}
	cout << result;
}