20438

날짜 : 2023. 04. 11

사용 언어 : python

 

문제

 

코드

import sys

n, k, q, m = map(int, sys.stdin.readline().split())  # 학생수, 졸고 있는 학생, 출석코드 학생, 구간 수
check = [False] * (n + 3)
sleep = list(map(int, sys.stdin.readline().split()))  # 조는학생 입장번호
attend = list(map(int, sys.stdin.readline().split()))  # 출석학생 입장번호

for i in attend:
    if i in sleep: continue  # 졸고 있는 학생 -> 생략
    for j in range(i, n+3, i):
        if j in sleep: continue
        check[j] = True  # 체크

cnt = 0  # 출석 안한 사람들
res = [0] * (n + 3)
for i in range(3, n + 3):
    if not check[i]:
        cnt += 1
    res[i] = cnt
#print(res)

for _ in range(m):
    s, e = map(int, sys.stdin.readline().split())
    if check[s]:
        print(res[e] - res[s])
    else:
        print(res[e] - res[s] + 1)

 

 

풀이

- 조는학생, 출석할 학생의 값을 입력받은 후 출석체크를 진행한다.(check)

- 이후 출석을 하지 않는 케이스를 누적합으로 계산하여 리스트에 저장한 후에 s, e를 각각 입력받아 값을 출력한다.

- 다만 인덱스 s의 경우 출석했을 때의 여부에 따라 값이 달라지기 때문에 조건문을 달아 1을 가산하거나 그냥 출력한다.

 

 

알게된 점

- 시간초과의 압박때문에 많이 고민했지만 n값이 5000까지라는 것을 확인하고 바록 DP로 들어갔다.

- 이후 테스트케이스를 시험하다 계속 값이 다르게 나와 애를 먹었지만 조건문 분기를 통해 해결할 수 있었다.

 

 

참고 사이트

-