[백준] 20438번 출석체크(python)(누적합)

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

20438번: 출석체크

 

1. 난이도 실버2 (🥈) 

 

2. 내가 작성한 풀이

구간합을 이용한 문제다! 나름 잘 풀었다고 생각했는데, 다른 분들이 푼 거랑 시간차이가 무려 4배가 나서 내 코드보단 수정 코드 참조하시길 추천ㅡ,,,

 

n,k,q,m = map(int,input().split()) #n학생수 k졸고 있는 q출석코드 m구간수

dp = [0,0,0] + [0] * (n+1) #구간합 저장

sleep = list(map(int, input().split())) #졸고 있음
connect = list(map(int, input().split())) #지환이가 연락함
connect = list(set(connect) - set(sleep)) #지환이가 연락한 사람 중 졸고 있는 사람이 있으면 뺌

result = 0

for i in range(3,n+4):
  if i in sleep: #졸고 있는 학생인 경우
    result+=1
    dp[i] = result
    continue

  check = 0
  for j in connect: #졸고 있지 않으며, 지환이가 연락한 번호의 배수인 경우
    if i % j == 0:
      check+=1

  if check == 0: #졸고 있지 않지만, 연락받지 못한 경우
    result+=1
    dp[i] = result

for i in range(m): #범위에 맞는 구간합 구하기
  a,b = map(int, input().split())
  print(max(dp[:b+1]) - max(dp[:a]))

 

3. 수정 코드

import sys
input = sys.stdin.readline

n,k,q,m = map(int,input().rstrip().split()) #n학생수 k졸고 있는 q출석코드 m구간수

sleep = [False] * (n+3)
connect = [0] * (n+3)

for i in map(int, input().rstrip().split()): #졸고 있는 학생 체크
  sleep[i] = True

for j in map(int, input().rstrip().split()):
  if sleep[j]:
    continue
  for k in range(j, n+3, j):
    if sleep[k] == False:
      connect[k] = 1

prefix = [connect[0]]

for i in range(1,n+3): #구간합
  prefix.append(prefix[-1] + connect[i])

for _ in range(m):
  s,e = map(int, input().rstrip().split())
  print(e-s+1 - (prefix[e] - prefix[s-1])) #전체에서 구간 중 출석