[누적합] 출석체크

문제링크

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

20438번: 출석체크

1. 핵심

• 학생의 분류
  • 출석 코드 받고 졸지 않은 학생 → 자신의 배수 번호에 전파 가능
  • 출석 코드를 받고 졸은 학생 → 전파 불가 / 코드 받을 수 없음
  • 출석 코드를 받지 않고 졸지 않은 학생 학생 → 전파 불가 / 코드는 받을 수 있음
  • 출석 코드를 받지 않고 졸은은 학생 → 전파 불가 / 코드 받을 수 없음
  • 코드 해설
    • 코드를 받은 학생들 중에서 졸은 학생은 code를 전파할 수 없으므로 continue로 넘어간다.
    • 코드를 받은 학생이 자신의 배수에 전파를 하는데 졸은 학생은 코드를 받을 수 없으므로 continue로 넘어간다.
• ★ 특정 구간([s, e])에서 특정한 것의 개수 찾기 ( 시간복잡도: O(N) )
  • 이 문제에서는 특정 구간에서의 1의 개수를 찾는게 목표였다.
  • psum를 정의: 인덱스i번째까지 누적된 1의 개수 > 그런데 항상 psum의 인덱스0번째는 0으로 비워 놓는게 좋다.
  • check: 0 1 0 0 1 1 0 0 1 0
  • psum: '0' 0 1 1 1 2 3 3 3 4 4
  •  psum[i + 1] = psum[i] (바로 직전까지의 누적된 1의 개수) + check[i] (1이면 +1, 0이면 +0) ( 0<= i < n)
  • 특정구간에서 1의 개수를 찾아보자. 예를 들어, 인덱스 5 ~ 6 구간의 1의 개수는 2개이다. 
    • psum의 정의를 생각하면
      • psum[6]은 인덱스0 ~ 인덱스6까지의 1의 개수이다.
      • psum[5]는 인덱스0 ~ 인덱스5까지의 1의 개수이다.
    • 따라서 인덱스 5 ~6 구간의 1의 개수는  psum[6] - psum[4]를 해야한다.
  • 따라서 특정 구간에서 특정한 것의 개수를 찾는 방법은 누적해서 더한 후에 특정 구간([s, e])에 psum[e] - psum[s - 1] 하기

2. 코드(Python)

# 3 ~ n + 2 입장번호 제공
# 한 학생에게 출석코드를 보내게 되면,
# 하댕 학생은 본인의 입장 *번호의 배수*인 학생들에게 출석코드를 보내어 해당 강의 출석하게끔!

# k명의 졸고 있는 학생들은 출석 코드를 제출하지 않고, 다른 학생들에게 보내지 않는다.
# 학생의 수 n, 졸고 있는 학생의 수 k, 지환이가 출석 코드를 보낼 학생의 수 q, 주어질 구간의 수 m
n, k, q, m = map(int, input().split())
sleep_students = list(map(int, input().split()))
code_students = list(map(int, input().split()))
qs = [list(map(int, input().split())) for _ in range(m)]


def solution(n, k, q, m, sleep_students, code_students, qs):
    check = [1 for _ in range(n + 3)]

    sleep_students = set(sleep_students)
    # 5000(q) * ( 5000(k) +  5000(n) * 5000(k) )
    # 5000 * 5000 * (1 + 5000) > 5000^3: 시간초과
    # 5000 * (1 + 5000 * 1) > 5000^2 >25 10^6 = 2.5  * 10^7
    for code in code_students:
        # 자는 애는 전파 불가
        if code in sleep_students:
            continue
        for x in range(code, n + 3, code):
            # code는 전파되는데 자는 애는 받으면 안된다.
            if x in sleep_students:
                continue
            check[x] = 0
    # qs: 50000 * 5000 (n + 3) > 25 * 10^7 > 2.5 * 10^8
    # 특정 구간의 1의 개수 찾기
    # 1 2 3 4 5 6 7 8 9 10
    # 0 1 0 0 1 1 0 0 1 0
    # 누적합의 정의는 처음부터 내 위치까지의 1의 개수
    # '0' 0 1 1 1 2 3 3 3 4 4
    # 예를 들어 5 ~ 6 번 구간에 1이 몇 개의 1이 존재하냐?
    # f(6번) = 1번 위치에서의 1의 개수 + ... + 6번 위치에서의 1의개수
    # f(5번) = 1번 위치에서의 1의 개수 + .. + 5번 위치에서의 1의 개수
    # 5 ~ 6번구간 1의 개수 = f(6번) - f(4번) = 6번 위치에서의 1의 개수 + 5번 위치에서의 1의 개수
    check = check[3:] 
    psum = [0] * (n + 1)
    # psum[1] = psum[0] + check[0]
    for i in range(n):
        psum[i + 1] = check[i] + psum[i]

    for q in qs:
        s, e = q
        print(psum[e - 2] - psum[s - 3])


solution(n, k, q, m, sleep_students, code_students, qs)