백준 1253 좋다 (c++) : 피너클

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

투포인터 문제다.

7

-1 -1 0 0 1 1 2

이렇게 입력이 들어왔다고 가정해보자.

 

나는 가장 왼쪽에 있는 -1부터 좋은 수 인지 확인할것이다.

-1 과 2를 확인한다. 합은 1이다. 목표는 -1이다. 합이 목표보다 크다.

-1 과 1을 확인한다. 합은 0이다. 목표는 -1이다. 합이 목표보다 크다.

-1 과 0을 확인한다. 합은 -1이다. 목표는 -1이다. 합과 목표가 같다.

이러면 -1은 좋은수인것이다.

 

이번에는 -1 오른쪽에 있는  -1을 확인하고 

그 다음에는 0을 확인하고

그 다음에는 0 오른쪽에 있는 0을 확인하고 이런식으로 쭉 가면 된다.

 

cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
int ans = 0;

값을 입력받고 정렬해준다. ans에는 좋은수의 개수가 들어갈 것이다.

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

int i는 목표이다. 위에서 목표가 -1이었던것과 같다.

int i = 0이라면 들어온 수 배열이 -1 -1 0 0 1 1 2이니 a[0] = -1, 즉 목표는 -1이고

int i = 2이라면 들어온 수 배열이 -1 -1 0 0 1 1 2이니 a[2] = 0, 즉 목표는 0이다.

start 는 0이고 end는  n-1이다. start는 i+1이 아니다. i+1로 하면 음수가 있을때가 힘들어진다.

만약 start나 end가 i와 같다면 1을 더하거나 빼준다.

		while (start < end) {
			
			int sum = a[start] + a[end];
			if (sum == a[i]) {
				ans++;
				break;
			}
			else if (sum > a[i]) end--;
			else start++;

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

start가 end보다 작은 동안만 반복문을 돌리며

start와 end의 합을 구해 목표와 비교해가며

합이 목표보다 크면 end - 1 을 해주고 합이 목표보다 작으면 start + 1을 해준다.

합이 목표와 같다면 ans + 1 을 해주고 반복문을 빠져나온다.

마지막에 start와 end를 한번더 i와 확인해준다

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;
int a[2001];

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

	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	int ans = 0;

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

		while (start < end) {
			
			int sum = a[start] + a[end];
			if (sum == a[i]) {
				ans++;
				break;
			}
			else if (sum > a[i]) end--;
			else start++;

			if (start == i) start++;
			if (end == i) end--;
		}
	}
	cout << ans << endl;
}

전체코드다.