[백준] 1253번 : 좋다

---

🔗문제 링크

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

1253번: 좋다

👩‍💻코드

#include <iostream>
#include <algorithm>
#include <vector>
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 count = 0;
    
    for(int i=0; i<N; i++){
        long find = A[i];
        int start_index = 0;
        int end_index = N-1;
        
        while(start_index < end_index){
            if (A[start_index] + A[end_index] == find){
                if (start_index != i && end_index != i){
                    count++;
                    break;
                }else if (start_index == i){
                    start_index++;
                }else if (end_index == i){
                    end_index--;
                }
            } else if (A[start_index]+A[end_index] < find){
                start_index++;
            } else{
                end_index--;
            }
        }
    }
    
    cout << count << "\n";
}

✏️문제 풀이

Do it! 알고리즘 코딩테스 - C++ 편 : 기출 유형 분석부터 문제 풀이 비법까지!를 참고하였습니다.

⭐[백준] 1940번 : 주몽과 [백준]  2018번 : 수들의 합 5 풀이를 참고해주세요.

 

위 두 문제와 투 포인터 알고리즘을 사용하는 것은 동일합니다.

배열을 정렬후 하나의 포인터는 앞에서부터 다른 하나의 포인는 뒤에서부터 시작합니다.

다만 주의 할 점은 자기 자신이 포함되는 경우는 제외해야 한다는 점입니다.