[백준 C++] 3273. 두 수의 합

문제 링크

---

3273번: 두 수의 합

접근 방법

---

서로 다른 정수이므로 정렬을 한 후, 정렬한 수열의 양 끝에서부터 두 수의 합이 x와 같은지 확인합니다.

소스 코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int n, s, e, sum, cnt = 0, target;
    cin >> n;

    vector<int> num(n);
    for (auto &a : num)
        cin >> a;
    cin >> target;
    
    sort(num.begin(), num.end());
    s = 0; // 시작 인덱스
    e = n - 1; // 끝 인덱스

    while (s < e)
    {
        sum = num[s] + num[e];

        if (target > sum) // x 보다 작을 때
            ++s;

        else if (target < sum) // x 보다 클 때
            --e;
            
        else // x 와 같은 경우
        {
            ++cnt;
            --e;
        }
    }

    cout << cnt;

    return 0;
}

코드 설명

---

배열의 크기가 최대 100000 이므로 이중 for 문으로 두 수의 합을 구하게 된다면 n²이기 때문에 10,000,000,000번의 연산을 하게 됩니다. 대략 1억 번의 연산이 1초이므로 이중 for문으로는 풀지 못함을 알 수 있습니다.

따라서 정렬을 한 후, 먼저 시작 인덱스(s)의 수와 끝 인덱스(e)의 수를 더한 다음, x 보다 크면 e를 감소시키고,  x 보다 작다면 s를 증가시킵니다.

시작 인덱스가 끝 인덱스 보다 작아야 하므로 while문의 조건을 s < e 로 했습니다.