[백준 20438번] 출석체크

[백준 20438번] 출석체크

www.acmicpc.net/problem/20438

20438번: 출석체크

 

 

 문제

 코로나 바이러스로 인해 H 대학은 비대면 강의를 실시하고 있다. 조교를 담당하게 된 지환이는 출석체크 방식을 바꾸려고 한다.

 학생들은 접속 순서대로 3번부터 N + 2번까지 입장 번호를 받게 된다.

 지환이가 한 학생에게 출석 코드를 보내게 되면, 해당 학생은 본인의 입장 번호의 배수인 학생들에게 출석 코드를 보내어 해당 강의의 출석을 할 수 있게끔 한다.

 하지만, K명의 졸고 있는 학생들은 출석 코드를 제출하지 않고, 다른 학생들에게 보내지 않는다.

 지환이는 무작위로 한 명의 학생에게 출석 코드를 보내는 행위를 Q번 반복한 뒤, 출석부 정리를 위해 특정 구간의 입장 번호를 받은 학생들 중에서 출석이 되지 않은 학생들의 수를 구하고 싶다.

 많은 인원을 담당해서 바쁜 지환이를 위해 프로그램을 만들어주자!

 

 입력

 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000)

 2번째 줄과 3번째 줄에 각각 K명의 졸고 있는 학생의 입장 번호들과 Q명의 출석 코드를 받을 학생의 입장 번호들이 주어진다.

 4번째 줄부터 M개의 줄 동안 구간의 범위 S, E가 공백을 사이에 두고 주어진다. (3 ≤ S < E ≤ N + 2)

 

 출력

 M개의 줄에 걸쳐서 각 구간에 대해서 출석이 되지 않은 학생들의 수를 출력하라.

 

 

 풀이

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int N, K, Q, M;
	cin >> N >> K >> Q >> M;
	
	int arr[5003] = {0,};
	bool sleep[5003] = {false,};
	for(int i=0;i<K;i++){
		int a; cin >> a;
		sleep[a] = true;
	}
	
	for(int i=0;i<Q;i++){
		int a; cin >> a;
		int k = 1;
		if(!sleep[a]){
			while(a * k <= N+2){
				if(!sleep[a * k]) arr[a * k] = 1;
				k++;
			}
		}
	}

	int sum[5003] = {0,};
	for(int i=3;i<=N+2;i++){
		sum[i] = sum[i-1] + arr[i];
	}
	
	for(int i=0;i<M;i++){
		int a, b; cin >> a >> b;
		cout << (b-a+1) - (sum[b] - sum[a-1]) << '\n';
	}
	return 0;
}

 문제에서 요구하는데로 구현만 하면 1단계는 통과이다. 처음에는 어떤 학생이 조교로 부터 출섹코드를 받으면 그 학생의 배수인 번호의 학생들에게 출석코드를 보내는 것에서 조는 학생이 있으면 거기서 멈춘다고 생각하여 틀렸었다. 또 문제를 제대로 안읽어서 학생의 번호가 3번부터 시작한다는 것을 못봐 두번째로 틀렸다. 너무 마음대로 생각한 것 같다.

 답을 구하는 과정은 어렵지 않으나 이 과정을 여러번 요구하는 것이 문제의 핵심이다. 요구할 때마다 과정을 거쳐 답을 구하게 되면 시간초과가 나기때문에 이럴때 누적합의 방법을 이용할 수 있다. sum[i]는 i번째 학생까지 출석체크를 한 인원의 수를 나타낸다. 원하는 구간의 인원수에서 이 누적합을 빼줌으로써 여러번의 과정을 생략하여 시간을 단축할 수 있다.