[C++/Baekjoon] 1253번: 좋다

문제

---

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

 

입력

---

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

 

출력

---

좋은 수의 개수를 첫 번째 줄에 출력한다.

 

 

풀이

---

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

int arr[2000];

int main(void){
	//배열 입력 받기
    int n;
    cin>>n;
    for (int i=0;i<n;i++)
        cin>>arr[i];
    sort(arr, arr+n); //오름차순 정렬

    int val, cnt=0;
    for (int i=0;i<n;i++){
        val=arr[i];
        int l=0,r=n-1,sum;
        while(l<r){ //왼쪽 포인터와 오른쪽 포인터가 만나기 전까지
            sum=arr[l]+arr[r];
            //두 수의 합으로 수가 만들어진다면 다른 두 수가 맞는지 확인 후 cnt 증가
            if(sum==val){
                if(l!=i&&r!=i){
                    cnt++;
                    break;
                }
                //해당 수라면 포인터 이동
                else if(l==i) l++;
                else if(r==i) r--;
            }
            //합이 더 적다면 왼쪽 포인터를 크다면 오른쪽 포인터를 이동
            else if(sum<val) l++;
            else r--;
        }
    }
    cout<<cnt;

    return 0;
}

 

포인터를 두 개를 생성하여 리스트에 순차적으로 접근하는 것을 투포인터라고 한다.

이러한 투포인터 알고리즘을 위해 오름차순 정렬이 필요하다.

코드 분석은 주석 참고

 

문제해결 조건보다 예외 조건을 잘 체크하는 습관을 들여야겠다.