[BOJ] 18114번 : 블랙 프라이데이 C++ 풀이

투포인터로 해결한 문제이다.

N개의 물건 가격이 주어진다. 이때 1, 2, 3개 중 하나를 선택해 총 무게를 K로 만들 수 있는지 묻고 있다. N의 제한이 5000이하이기 때문에 2개를 선택하는 경우까지는 확인할 수 있지만, 3개를 선택하는 것이 관건이다.

정확히 K를 맞춰야 하는 것에 집중해보자. 그리고 하나의 물건을 기준으로 잡자. 이 무게를 X라고 할때 우리는 2개의 물건을 더했을때 N-K가 나오는 조합이 있는지 확인해야 하고 2개의 합이 N-K인지 확인하기 위해 투 포인터를 사용한다면, O(N)에 N-K 값이 있는지 알 수 있다. 따라서 O(N^2)에 3개를 선택한 경우도 구할 수 있다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 2000000000
#define MOD 10007
#define NUM 100010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
int N, K;
bool flag = false;
vector<int> v;

void init() {  
    cin >> N >> K;
    for (int i=0; i<N; i++) {
        int x;
        cin >> x;
        v.push_back(x);
        if (x == K) flag = true;
    }
    sort(v.begin(), v.end());
    
    for (int i=0; i<N-1; i++) {
        int s = i+1, e = N-1;
        int sum = v[i];
        while (s < e) {
            int curr = sum + v[s] + v[e];
            if (curr == K) {
                flag = true;
                break;
            }
            if (curr < K) s++;
            else e--;
        }
    }

    for (int i=0; i<N-1; i++) for (int j=i+1; j<N; j++) if (v[i] + v[j] == K) flag = true;

    if (flag) cout << 1 << '\n';
    else cout << 0 << '\n';
} 

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