[백준] 20438 출석체크, python

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

20438번: 출석체크

동적계획법으로 누적합을 사용하는 문제이다.

출석체크 한 사람을 구한뒤에 출석하지 않은 학생을 하나하나 찾아서 계속 시간초과가 걸렸다.

누적합으로 구한뒤에 구간별로 출력하니 통과.

 

import sys; input = sys.stdin.readline

# 0 입력
N, K, Q, M = map(int, input().split())
sleep = set(map(int, input().split()))
students = set(map(int, input().split()))
attend = [False for _ in range(N + 3)]

# 1 출석 체크
for s in (students - sleep):
    for i in range(s, N + 3, s):
        if i not in sleep:
            attend[i] = True
# 2 미출석자 누적합 구하기
memo = [0 for _ in range(N + 3)]
for i in range(3, N + 3):
    if not attend[i]:
        memo[i] = memo[i - 1] + 1
    else:
        memo[i] = memo[i - 1]

# 3 출력
answer = ''
for _ in range(M):
    s, e = map(int, input().split())
    ans = memo[e] - memo[s - 1]
    answer += '{}\n'.format(ans)
print(answer)

C++도 큰 차이 없을거같아서 넘어간다.