(C++) - 백준(BOJ) 20438 : 출석체크

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

20438번: 출석체크

누적합 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

학생 수 n, 조는 인원 k, 출석코드를 받은 학생 수 q, 구간 개수 m, 구간 s와 e, 정답을 출력할 ans, 학생 vector, map sleep, attend를 선언후 입력받습니다.

📔 풀이과정

* 5000의 학생 수에 대해 50000개의 구간이 들어온다면 brute force로 탐색 시 2억 5천이므로 시간초과입니다. 이는 누적합으로 O(1)만에 구할 수 있습니다.* 출력이 많으므로 c와 동기화를 끊어줍니다.

📔 정답출력

매 구간 s e마다 누적 구간을 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n, k, q, m, s, e, ans;
vector <int> student;
map <int,int> sleep, attend;
int main(){
    fastio;
    cin >> n >> k >> q >> m;
    student.resize(n+3, 1);
    student[2] = 0;
    for(int i = 0, x; i < k; i++) {
        cin >> x;
        sleep[x] = 1;
    }
    for(int i = 0, x; i < q; i++) {
        cin >> x;
        attend[x] = 1;
    }
    
    for(auto a : attend){
        int tmp = a.first;
        if(sleep[tmp]) continue;
        for(int i = 1; tmp <= n+2; i++){
            if(!sleep[tmp])
                student[tmp] = 0;
            tmp = i*a.first;
        }
    }
    
    for(int i = 3; i <= n+2; i++){
        student[i] += student[i-1];
    }
    
    for(int i = 0; i < m; i++){
        cin >> s >> e;
        cout << student[e] - student[s-1] << '\n';
    }
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.