[BOJ] [Python] 20438 : 출석체크

문제를 정리해보자.

 

 

3번부터 (N + 2)번까지 있다.

 

지환이가 무작위로 선정한 학생을 i라고 하자.

i번은 i번의 배수인 학생들에게 출석 코드를 보낸다.

(i는 Q번 바뀐다.)

 

현재 K명은 졸고 있다.

졸고 있는 학생은 출석도 안 하고, 출석 코드를 보내지도 않는다. 

 

최종적으로 출석이 되지 않은 학생들의 수를 구하면 된다.

 

# N : 학생 수
# K : 졸고 있는 학생 수
# Q : 지환이가 출석 코드를 보낼 학생 수
# M : 주어질 구간의 수

import sys
input = sys.stdin.readline

n, k, q, m = map(int, input().split())

k_li = list(map(int, input().split()))
q_li = list(map(int, input().split()))

dp = [1] * (n + 3)

while q_li:
    start = q_li.pop(0)

    if start not in k_li:
        for num in range(1, ((n + 2) // start) + 1):
            if start * num not in k_li:
                dp[start * num] = 0


dp_sum = [0] * (n + 3)

for num in range(3, n + 3):
    if num == 3:
        dp_sum[num] = dp[num]

    else:
        dp_sum[num] = dp[num] + dp_sum[num - 1]


for _ in range(m):
    i, j = map(int, input().split())
    print(dp_sum[j] - dp_sum[i - 1])

 

 

dp 리스트는 현재 1로 초기화 되어 있다.

출석 체크를 한 학생은 dp 리스트의 자신의 값이 0으로 바뀐다.

 

최종적으로 dp리스트에 1은 출석 체크를 하지 못한 학생들이다.

 

이 문제의 핵심은 지금부터이다.

특정 구간의 범위 S, E가 주어지는데, 이 구간에 1의 개수를 구해야 한다.

 

방법은 2가지로 생각할 수 있다.  (구간 개수 : M, 길이 : N)

 

 

첫 번째 방법은, 범위가 주어질 때마다 범위 내에 있는 1의 개수를 세보는 것이다.

시간 복잡도를 생각해보면 O(M x N) 이고,

 50,000 x 5,000 이라서 250,000,000이다.

 

제한 시간이 0.1초라서 이 방법은 시간초과가 날 것이다.

 

 

두 번째 방법은 부분합이다.

 

부분합을 이용해서  S(s~e)을 구한다면, S(s~e) = S(s) - S(1~(e-1))로 구하면 된다.

 

이를 위해서는,

3부터 N + 2까지의 위치마다,

1부터 그 위치까지의, 1의 개수를 따로 저장해줘야 한다.

 

for num in range(3, n + 3):
    if num == 3:
        dp_sum[num] = dp[num]

    else:
        dp_sum[num] = dp[num] + dp_sum[num - 1]

 

위 처럼 dp를 이용했다.

 

 

for _ in range(m):
    i, j = map(int, input().split())
    print(dp_sum[j] - dp_sum[i - 1])

 

부분합으로 구하니, 시간 복잡도는 O(M + N)이다. 

 

 

 

 

 

+ 하지만 이 문제는 부분합으로 풀어도 시간초과가 난다. 

 

M이 50,000이나 되기 때문에

입력받는 부분에서 시간초과가 나는 것이다.

 

해결 방법은 아래와 같다.

 

import sys
input = sys.stdin.readline