[C++] 백준 1253번: 좋다

🔗 문제

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

 

 

✏️ 풀이

실질적으로 N은 2000개 밖에 되지 않지만 나이브하게 생각할 수 있는 for문으로는 O(N^3)으로 무리가 있다.

2개의 값을 가리켜야 한다는 점을 고려하면 투포인터가 적합하다.

 

#시간 복잡도 계산

• 투포인터를 사용하기 위해 정렬이 필요하다. ⇒ O(nlogn)
• N개의 값에 대한 최대 N번을 고려한다. ⇒ O(N^2)

 

수열에 음수가 있을 때 답이 나오지 않는다는 것을 발견했다

3
-3 0 3
// 1 (0)

3
-2 -1 -1
// 1 (-2)

 

 

 

i번째 수열은 0부터 N-1의 범위를 모두 보아야 한다. 

이 때 자기 자신을 가리키지 않도록 조건 체크를 반드시 해주어야 한다. 

 

 

 

💾  소스

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

vector<long long> input;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N, answer = 0;

    cin >> N;
    input.resize(N, 0);
    for(int i=0; i<N; ++i)
    {
        cin >> input[i];
    }

    sort(input.begin(), input.end());

    for(int i=0; i<N; ++i)
    {
        int start = 0;
        int end = N-1;
        int key = input[i];

        while(start < end)
        {
        	// 자기 자신은 제외
            if (start == i) start++;
            else if(end == i) end--;

			// 포인터 이동 후에도 조건 체크
            if(start >= end) continue;

            int cur = input[start] + input[end];
            if(key == cur)
            {
                ++answer;
                break;
            }

            if(key > cur)
            {
                ++start;
            }
            else
            {
                --end;
            }
        }

    }

    cout << answer;
    return 0;
}