백준 20438 출석체크 c++, Kotlin (누적 합) 2022-06-14추가

문제 출처 : https://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개의 줄에 걸쳐서 각 구간에 대해서 출석이 되지 않은 학생들의 수를 출력하라.

알고리즘 분류

• 누적 합

풀이

누적합 문제이다.

우선, 문제를 잘못 이해했던 게,

지환이가 무작위로 선택한 학생이 자고 있으면 해당 학생은 출석도 안 되고, 뒤에 전달하지도 않는다.

지환이가 무작위로 선택한 학생이 자고 있지 않으면, 해당 학생은 출석되고 뒤에 전달하는데 전달받은 학생이 자고 있다면, 그 학생만 출석할 수 없고, 뒤에 학생들은 계속 이어서 첫 번째 학생에게 전달받는 것이다.

이 조건을 잘못 이해해서 계속 틀렸었는데, 문제 난이도는 높지 않다.

 

우선, 자고 있는 학생들을 bool sleep[]에 저장해 주고,

지환이가 선택한 학생들은 출석 및 본인의 배수 학생들에게 전달한다.

이때, 만약 지환이가 선택한 학생이 자고 있다면, 출석 및 전달 X //지환이의 학생 선택 반복문 continue;

지환이가 선택한 학생이 자고 있지 않다면, 출석 및 전달O // int pSum[]에 출석 완료되면 0 저장, 출석 안 되면 1인 상태

선택한 학생이 본인의 배수의 학생들에게 전달하는데 배수의 학생이 자고 있다면 해당 학생만

// 선택된 학생의 뒤로 전달 반복문 continue;

 

이후, 4부터 N+2까지 pSum[i] = pSum[i-1]으로 출석되지 않은 학생들에 대한 누적 합을 완성하고,

pSum[end]-pSum[start-1]로 start~end 구간의 출석되지 않은 학생들을 빠르게 구할 수 있다.

누적 합을 사용하지 않는다면, 매번 start~end 구간을 반복해야 하므로 시간 초과가 나기 때문에 누적 합을 사용하는 것이다.

 

코드(c++)

#include <iostream>
using namespace std;
int N, K, Q, M;
//1<=KQ<=N<=5000
//1<=M<=50000
//N 학생의 수 K 졸고 있는 학생의 수, 출석 코드 보낼 학생의 수 Q, 주어질 구간의 수 M
bool sleep[5003];
int pSum[5003];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> K >> Q >> M;
	
	//자는 사람
	for (int i = 0; i < K; i++) {
		int num;
		cin >> num;
		sleep[num] = true;
	}
	//출석이 되지 않은 학생은 1로 초기화
	for (int i = 3; i <= N+2; i++) {
		pSum[i] = 1;
	}
	//출석처리(0)
	//자는 사람은 다음 사람에게 전달하지 않는다.X
	//num은 본인의 배수인 사람들에게 전달하며, 본인이 직접 전달한다. 즉, next가 자고 있으면 그 사람만 건너뛰고 뒤에 사람들 계속 전달.
	for (int i = 0; i < Q; i++) {
		int num;
		cin >> num;
		if (sleep[num])continue;
		int next = num;
		while (next <= N+2) {
			if (sleep[next]) {
				next += num;
				continue;
			}
			pSum[next] = 0;
			next += num;
		}
	}
	for (int i = 4; i <= N+2; i++) {
		pSum[i] += pSum[i - 1];
	}
	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		cout << pSum[end] - pSum[start - 1]<<'\n';
	}

	return 0;
}

코드(Kotlin)

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()){

    //input
    val (n,k,q,m) = getIntList()
    val sleep = BooleanArray(n+3)
    val pSum = IntArray(n+3){1}
    pSum[0] = 0
    pSum[1] = 0
    pSum[2] = 0
    getIntList().forEach {
        sleep[it] = true
    }
    //solve
    getIntList().apply {
        for(origin in this) {
            if(sleep[origin]) continue
            var num = origin
            while(num in pSum.indices) {
                if (sleep[num]) {
                    num+=origin
                    continue
                }
                pSum[num] = 0
                num+=origin
            }
        }
    }
    for(i in 4 until pSum.size){
        pSum[i] += pSum[i-1]
    }
    //output
    repeat(m) {
        getIntList().apply {
            write("${pSum[this[1]] - pSum[this[0]-1]}\n")
        }
    }

    close()
}