3273번_두 수의 합_BOJ

문제 링크

3273번 두 수의 합 : https://www.acmicpc.net/problem/3273

문제 설명 및 해결 아이디어

두 수의 합을 구하는 문제이다. lo, hi변수를 두어 탐색하면서 푼 첫번째 방법과, lower_bound와 upper_bound를 이용하여 푼 두번째 방법이 있다.

두번째 방법의 경우, break 조건(a > x/2, a*2==x)을 주의하자.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, x, num;
vector<int> vt;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num);
        vt.push_back(num);
    }
    sort(vt.begin(), vt.end());
 
    scanf("%d", &x);
 
    int cnt = 0, lo = 0, hi = vt.size() - 1;
    while (lo < hi) {
        if (vt[lo] + vt[hi] == x) {
            cnt++; lo++; hi--;
        }
        else if (vt[lo] + vt[hi] < x) {
            lo++;
        }
        else if (vt[lo] + vt[hi] > x) {
            hi--;
        }
    }
    printf("%d\n", cnt);
    return 0;
}
 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, x, num, res;
vector<int> vt;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num);
        vt.push_back(num);
    }
    sort(vt.begin(), vt.end());
 
    scanf("%d", &x);
    for (int a : vt) {
        if (a > x / 2)
            break;
        if (a * 2 == x) {
            int b = upper_bound(vt.begin(), vt.end(), a) - lower_bound(vt.begin(), vt.end(), a);
            res += b*(b - 1) / 2;
            break;
        }
        int b = x - a;
        res += upper_bound(vt.begin(), vt.end(), b) - lower_bound(vt.begin(), vt.end(), b);
 
        if (a == b)
            res--;
    }
    printf("%d\n", res);
    return 0;
}