[BOJ/C++] 좋다(1253번)

1. 개요

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

1253번: 좋다

1-1. 설명

N개의 수 중 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 좋다고 한다. N개의 수가 주어지면 그 중 좋은 수의 개수는 몇개인지 출력하는 프로그램을 작성한다.

1-2. 제한 사항

 - 첫 줄에 수의 개수 N이 주어지며, N은 1 이상 2,000 이하

 - 둘째 줄에는 i번째 수를 나타내는 A_i가 N개 주어짐

---

2. 구현

2-1. 풀이

풀이는 이분탐색과 투포인터로 나눠지는데, 투포인터를 선택해 풀었다. 초반에 정렬을 신경쓰지 않아 살짝 헤맸으나, 금방 문제점을 찾아 고쳐나갔다. 

2-2. 코드

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

int nums[2001];
int result, N;

void twoPointer(int start, int end, vector<int> vec, int value);

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

    vector<int> subVec;
    cin >> N;
    result = 0;
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }
    sort(nums, nums + N);
    for (int i = 0; i < N; i++) {
        vector<int> subVec(nums, nums + N);
        subVec.erase(subVec.begin() + i);
        twoPointer(0, N-2, subVec, nums[i]);
    }
    cout << result;
    return 0;
}

void twoPointer(int start, int end, vector<int> vec, int value) {
    int curSum = 0;

    while (start < end) {
        curSum = vec[start] + vec[end];
        if (curSum > value) end -= 1;
        else if (curSum < value) start += 1;
        if (curSum == value) {
            result += 1;
            break;
        }
    }
}