백준: Class 6 - 16287

</br> 클래스 6 계속
</br>

16287: Parcel

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

방법 1.

    int w, n;
    cin >> w >> n;

    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            v.push_back(make_tuple(nums[i] + nums[j], i, j));
        }
    }

    sort(v.begin(), v.end());

    bool chk = false;
    int l = 0, r = v.size()-1;
    while( l < r ){
        if( get<0>(v[l]) + get<0>(v[r]) == w ){
            if( get<1>(v[l]) != get<1>(v[r]) && get<1>(v[l]) != get<2>(v[r])
               && get<2>(v[l]) != get<1>(v[r]) && get<2>(v[l]) != get<2>(v[r]) ){
                chk = true;
                break;
            }
            else l++;
        }
        else if( get<0>(v[l]) + get<0>(v[r]) < w ) l++;
        else r--;
    }

    if( chk ) cout << "YES\n";
    else cout << "NO\n";

투 포인터로 풀어 봤다
시간 초과 난다 왜??
n이 최대 5000이면 5000C2 = 12497500으로, 두 개의 합 구하는데 한 번, 투 포인터 돌리는데 한 번 해서 O(12497500*2)가 될 줄 알았는데

그런데 생각해 보니 정렬을 까먹었다 O(NlogN)이면 꽤 걸린다
실제로 ideon(https://ideone.com/ceKWah)에 돌려 보니 그냥 정렬만 해도 0.98초 걸림

</br>

방법 2.

#include <bits/stdc++.h>

using namespace std;

int nums[5001];
int x[400001];
int y[400001];

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

    int w, n;
    cin >> w >> n;

    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }

    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            int k = nums[i] + nums[j];
            x[k] = i;
            y[k] = j;
        }
    }

    bool chk = false;
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            int k = w - nums[i] - nums[j];
            if( k < 0 || 400000 < k || (x[k] == 0 && y[k] == 0) ) continue;
            if( x[k] != i && x[k] != j && y[k] != i && y[k] != j ){
                chk = true;
                break;
            }
        }
    }

    if( chk ) cout << "YES\n";
    else cout << "NO\n";

}

그래서 문제 힌트를 봤는데 dp라고 해서… 좀 다르게 생각해 봤다
각 원소 크기가 20만 이하니, 둘의 합은 40만 이하이므로 무게를 인덱스로 dp를 만들 수 있다.
그런데, 겹치는 애가 있으면 안 되니까

x[무게[i] + 무게[j]] = i
y[무게[i] + 무게[j]] = j

로 인덱스를 저장한다.

그리고 다시 포문을 똑같이 돌린다.
그러다가 만약 인덱스가 다 다른데 w - 두 무게 합이 존재한다면, 답이 있는 것이므로 YES가 된다.
</br>

---

처음에 투 포인터 생각하고 아 나 좀 치네ㅋㅋ 한 내가 부끄럽다
열심히 하자
</br>