1940번_주몽

문제 링크

1940번 주몽 : https://www.acmicpc.net/problem/1940

문제 설명 및 해결 아이디어

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

두번째 방법의 경우, 같은 쌍을 두번씩 찾게 되므로 cnt의 반을 출력해야함을 주의하자.

코드

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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m, num;
vector<int> vt;
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num);
        vt.push_back(num);
    }
    sort(vt.begin(), vt.end());
 
    int cnt = 0;
    for (int h : vt) {
        if (binary_search(vt.begin(), vt.end(), m - h))
            cnt++;
    }
    printf("%d\n", cnt / 2);
    return 0;
}