[1940] 주몽

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

1940번: 주몽

배열에 개수를 기록해두고, a[i]와 a[m-i]의 최소값만큼 갑옷을 만들 수 있다.

i==(m - i)인 경우에는 2개씩 사용하므로, 이에 대한 예외처리에 주의할 필요가 있다.

배열을 천만개 잡고, 천만번 i를 돌려도 되지만, m>200'000인 경우에는 어처피 항상 만들 수 있는 갑옷이 없고,

양쪽에서 좁혀오듯 확인하며, 어처피 순열이 아니라 조합에 가까우니 m/2만 확인해도 된다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, ans, a[200001];

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    if (m > 200000) {

        cout << 0;

        return 0;

    }

    int i;

    for (i = 0; i < n; i++) {

        int x;

        cin >> x;

        a[x]++;

    }

    int S = m >> 1;

    for (i = 1; i <= S; i++) {

        if (i == m - i) {

            int S = a[i] >> 1;

            ans += S;

            a[i] -= S;

            continue;

        }

        int S = min(a[i], a[m - i]);

        ans += S;

        a[i] -= S;

        a[m - i] -= S;

    }

    cout << ans;

    return 0;

}

---