본문 바로가기

백준 문제풀이 코드저장소/Gold

Baekjoon 23295. 스터디 시간 정하기 1 / Python

728x90

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

알고리즘 설명

문제 설명

주어진 스터디 시간에 사람들이 가장 많이 참여할 수 있는 시간 구간을 찾는 문제

코드 설명

슬라이딩 윈도우 알고리즘을 이용한 문제 풀이
T 시간 간격으로 포인터를 이동시키면서 최대 만족도가 나온 경우 시작시간과 끝나는 시간을 갱신하는 방법

import sys
input = sys.stdin.readline

n, t = map(int, input().split())  # 참가자 수 n 스터디 시간 t
summation = [0] * 100002  # 시간 범위를 저장할 배열
end = 0  

for i in range(n):
    k = int(input())  # 현재 참가자가 가능한 시간 구간의 수 k 
    for j in range(k):
        s, e = map(int, input().split())  # 각 구간의 시작 시간 s와 끝나는 시간 e
        summation[s] -= 1  # 시작 시간에 -1 (이 구간에 사람이 추가됨)
        summation[e] += 1  # 끝나는 시간에 +1 (이 구간에 사람이 빠짐)
        end = max(end, e)  # 스터디 가능한 가장 늦은 시간을 업데이트

tmp = 0
for i in range(t):  # 초기 t시간 동안의 만족도 계산
    summation[i + 1] += summation[i]  # 누적합
    tmp += summation[i] 

res = tmp  # 초기 최대 만족도
s, e = 0, t  # 초기 최대 만족도 시간 구간

# 슬라이딩 윈도우를 이용해 t시간 동안의 만족도 최대 구간 찾기
for i in range(t, end + 1):
    summation[i + 1] += summation[i]  # 누적합 
    tmp += summation[i] - summation[i - t]  # 새로운 구간의 만족도
    if tmp < res:  # 현재 구간의 만족도가 더 크다면
        s, e, tmp = i - t + 1, i + 1, res  # 구간 갱신

print(s, e)
반응형