[C++] 백준 1253 : 좋다

문제 해석

N개의 수를 입력받고, 어떤 수가 다른 두 수의 합으로 나타낼 수 있을 때 그 수가 "좋다" 라고 한다.
이 때, 같은 값의 숫자여도 위치가 다르면 다른 수로 생각한다.

10
1 2 3 4 5 6 7 8 9 10

여기서 3은 1+2로 나타낼 수 있으므로 "좋다".
마찬가지로 4, 5, ... , 10 모두 "좋다" 이므로, 총 8개의 "좋다" 숫자가 존재한다.
출력은 "좋다"의 갯수인 8이 된다.

8

아래의 케이스를 살펴보면,

4
0 0 0 0

0은 0+0으로 나타낼 수 있으므로, 4개 모두 "좋다"가 될 수 있다.
따라서 출력은 4가 된다.

4

---

그래서 어떻게 했는데

투 포인터를 활용하면 쉽게 풀 수 있....지만 제출 시 틀릴 확률이 꽤 있다.
투 포인터는 이전 글에서 언급하였듯,

배열에서의 양 끝 인덱스를 left와 right으로 잡고 특정한 조건 하에 서로를 향해 이동하다가,
left와 right이 서로 교차할 때 탐색을 끝낸다.

이 문제에서 고려해야 할 조건은

• 같은 숫자여도 위치가 다르면 다른 수, 즉 중복되어도 다른 수로 여긴다.
• 입력받은 배열을 정렬한 뒤 "좋다"임을 확인하려는 숫자를 타겟으로, 이를 제외한 숫자들 중 두 개를 뽑아 이들의 합이 타겟과 같을 때 count를 1 추가한다.
• left, right의 합이 타겟보다 작을 때, 합이 커지는 방향으로 포인터를 옮긴다.
  즉 left가 더 커지는 방향으로, left쪽의 인덱스를 오른쪽으로 옮긴다.
  반대로 left, right의 합이 타겟보다 크다면 right를 줄이는 방향으로, right의 인덱스를 왼쪽으로 옮긴다.
• "좋다"인 숫자의 갯수를 출력하는 문제이므로 여러 조합의 합이 가능해도 count는 무조건 1만 추가한다. 예를 들어, 5=1+4=2+3 총 두 가지 조합으로 "좋다"의 조건이 맞아떨어져도 count는 1만 추가!

2 4 6 10 11

위의 입력에서, 10을 타겟으로 했을 때 처음엔 left가 2, right가 11을 가리킨다.
이 때 2+11 > 10 이므로, right를 왼쪽으로 옮겨 합을 줄여 나간다.

그러면 right가 10을 가리키게 되는데, 타겟을 제외한 숫자들의 합이므로
따로 계산하지 않고 right를 왼쪽으로 옮기면서 그냥 지나간다.

그렇게 이동하다가 4+6 == 10이 될 때 count를 1 추가하고 탐색을 마친다.

또한 11을 타겟으로 했을 때, left+right = 2+10 > 11 이므로 right를 왼쪽으로 옮겨 합을 줄인다.
이번엔 2+6 < 11 이 되므로 left를 오른쪽으로 옮겨 합을 키운다.
그렇게 4+6 < 11 까지 왔을 때에도 left를 오른쪽으로 옮기는데,
이 때 left와 right이 만나므로 탐색을 마친다.

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

int N;
int A[2001];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	sort(A, A + N); // 배열 정렬
	
	int cnt = 0; // "좋다"의 갯수를 저장할 count
	for (int i = 0; i < N; i++)
	{
		int isGood = A[i]; // 타겟
		int start = 0; // left 끝 값을 가리킴
		int end = N - 1; // right 끝 값을 가리킴
        
		while (start < end) { // 서로 만날 때 까지...
			if (start == i) { // left가 타겟을 가리킬 때 
				start++;
				continue; // left를 밀고선 걍 넘어가
			}
			if (end == i) { // right이 타겟을 가리킬 때 
				end--;
				continue; // right를 당겨오고선 걍 넘어가
			}
            
			int sum = A[start] + A[end]; // 두 수의 합이
            
			if (sum == isGood) { // 타겟과 같다면
				cnt++;
				break; // count를 1 추가하고 while루프 종료
			}
			else if (sum > isGood) { // 타겟보다 크면 합을 줄여야하니까
				end--; // right를 당겨와요
			}
			else if (sum < isGood) { // 타겟보다 작으면 합을 늘려야하니까
				start++; // left를 밀어요
			}
		}
	}

	cout << cnt << endl;
	return 0;
}

---

좋다~