[BOJ/C++] 1253(좋다)

1. Link

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

• 정렬 후 이분 탐색이라는 정석적인 문제입니다. 다만 투 포인터 형식을 조금 첨가한 문제라는 점으로 인해 단순하게 알고 있던 이분 탐색 코드와는 조금 다르게 풀어야 합니다.

• 특정 값보다 클 경우에 en = mid - 1, 작을 경우에 st = mid + 1을 하는 보통의 이분 탐색과 다르게 정렬된 값에서 특정 값을 찾기위한 행동이므로 ++st와 --en으로 대체됩니다.

2. 풀이 과정

1. 어떤 수가 다른 두 수의 합으로 나타낼 수 있다면 -> 이분 탐색, 투 포인터

• 0부터 n까지 각각 배열의 값에 맞는 두 수의 값을 이분 탐색합니다. 따라서 for문 내에 이분 탐색을 구현만 하면 됩니다.

• 예제를 들어 문제를 설명해보도록 하겠습니다.

위 내용에서 1, 그리고 2는 더해서 나올 수 없기 때문에 생략하겠습니다.

다음을 보면 3은 1+2로 가능하므로 좋은 수(결과값) 개수를 추가합니다.

4는 1+3으로 가능하니 결과값에 추가하고 넘어갑니다.

그렇게 진행되다 보면, 다음과 같이 마지막 구간에 도달합니다.
a[st] = 1, a[en] = 10이므로 1+10은 a[i]=10보다 큽니다. 따라서 en을 줄일 필요가 있겠습니다.

줄여서 다음과 같은 1+9==10이라는 결과를 얻는 것으로 좋은 수를 전부 구할 수 있습니다.

• (+추가) 위 예제만 보면 i=2부터 시작해서 0번째와 1번째 값은 덧셈으로 나올 여지도 없지 않나 싶겠지만, 같은 값이 중복으로 나와 0 0 0이 나오는 경우를 생각하면 i=0부터 계산해야 간결하게 코드를 작성할 수 있을 것입니다.

• map을 써서 풀 수 있을 것 같긴 합니다..만 뭔가 이분 탐색과 투 포인터를 직접 구현을 통해 풀어보고 싶었고, 실질적인 테스트는 아니었기에 다음과 같이 구현했습니다.

3. 정답 코드

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

int n;
vector<int> a;

void input() {
	cin >> n;
	int num;
	for (int i = 0; i < n; ++i) {
		cin >> num;
		a.push_back(num);
	}
	sort(a.begin(), a.end());
}

void solution() {
	input();
	if (n < 3) {
		cout << 0;
		return;
	}
	int answer = 0;
	for (int i = 0; i < n; ++i) {
		int st = 0, en = n - 1;
		while (st < en) {            
			if (st == i) {
				++st; continue;
			}
			if (en == i) {
				--en; continue;
			}
			int sum = a[st] + a[en];
			if (sum == a[i] && st != i && en != i) {
				++answer;
				break;
			}
			if (sum < a[i]) {
				++st;
			}
			else {
				--en;
			}
		}
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
 	solution();
	return 0;
}