[누적합] Good Bye, BOJ 2023! B. 거짓말 - 백준 31091번

31091번: 거짓말

이해하기 너무 빡쎘다…

k : 거짓말한 사람의 수

ex) k = 3일 때 → 거짓말한 사람 = “(k명 초과) 이상” and “(k명 이하) 이하 가 거짓말하는 사람이다”

1번째 시도 : k 마다 for문을 한번 더 돌렸을 때 ⇒ O(n^2) Timeout

Solution)

• k = 3일 때 → 거짓말한 사람 = “(k명 초과) 이상” and “(k명 이하) 이하 가 거짓말하는 사람이다”
• 즉) 3명이 거짓말 == “(k명 초과) 이상” + “(k명 이하) 이하 가 거짓말하는 사람이다”
• k = 음수(& 0)에서 거짓말하는 사람 + 양수에서 거짓말하는 사람
• “이상”, “이하” ⇒ 누적합(? 맹신 ㄴ)
• 중복이 있을 수 있으니 사람의 명수로 카운트 - 코드에서는 vector index에 카운트

#include <iostream>
#include <vector>

using namespace std;

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

    int N;
    cin >> N;

    vector<int> L(N + 1, 0);
    vector<int> U(N + 1, 0);

    for (int i = 0; i < N; ++i) {
        int x;
        cin >> x;
        if (x > 0) {
            U[x]++; // 0 1 1 0 0
        } else {
            L[-x]++; // 0 2 0 0 0
        }
    }
    // U : 0 1 1 0 0 양수 일때 1이랑 2가 on
    // L : 0 2 0 0 0 음수 일때 -1이 두번 on
    // 개수로 센다
    vector<int> LS(N + 1, 0);
    vector<int> US(N + 1, 0);

    LS[0] = 0;
    for (int i = 1; i <= N; ++i) {
        LS[i] = LS[i - 1] + L[i - 1];
    }

    US[N] = 0;
    for (int i = N - 1; i >= 0; --i) {
        US[i] = US[i + 1] + U[i + 1];
    }

    // US : 2 1 0 0 0
    // LS : 0 0 2 2 2

    vector<int> ans;
    for (int i = 0; i <= N; ++i) {
        if (US[i] + LS[i] == i) {
            ans.push_back(i);
        }
    }

    cout << ans.size() << '\n';
    for (int i : ans) {
        cout << i << ' ';
    }

    return 0;
}