백준 20438 자바 - 출석체크 (BOJ 20438 JAVA)

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

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/20400/BOJ_20438.java

  

 

1. 일단 잠자는 사람들을 생각하지 않고, 출석 코드를 보내는 부분만 생각해보자. n명을 입력받고, q를 입력받아 단순히 자신과 그 배수들은 출석코드를 받았다고 할 수 있다. 이 부분까진 간단하게 구현 가능할 것이다.

 

2. 다음으로 잠자는 사람에 대해 어떻게 처리해야할지 확인해보자. 일단 q명 중 출석코드를 받은게 자는사람에 포함되어 있다면 그 배수한테 출석코드를 보낼 수 없다. 따라서 이 경우 해당 출석 코드는 무시된다. (23line)

다음으로, 출석 코드를 받은 사람은 자고있지 않았지만, 그 배수번째 중 자는 사람이 있는 경우를 보자. 이 경우 어차피 출석 코드를 주는 사람이 코드를 주는 주체이므로, 그냥 자는 사람만 무시하고 돌리면 된다. (25~27line)

그럼 여기까지 누가 출석코드를 받았는지는 어렵지 않게 알 수 있다.

 

3. 그럼 m개의 쿼리에 대해 어떻게 답을 출력할지 생각해보자. 이 문제의 경우 단순히 주어진 범위 중 출석되지 않은 사람의 수만 구하면 된다. 그럼 출석되지 않은 사람을 1, 출석된 사람을 0 이라 두고 suffix sum (누적합) 배열을 만들면 범위 내의 출석되지 않은 사람의 수를 O(1)로 바로바로 구할 수 있다.

 

예를 들어 '예제 입력 1'에 해당하는 출석여부 배열은 다음과 같다. (출석되지 않은 사람을 1, 출석된 사람을 0)

그리고 suffix sum을 계산한 배열은 다음과 같다.

그럼 여기서 s와 e가 주어졌을 때, 구간내에 있는 출석되지 않은 학생은 arr[e]-arr[s-1] 로 구할 수 있다.