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)
반응형
'백준 문제풀이 코드저장소 > Gold' 카테고리의 다른 글
Baekjoon 1865. 웜홀 / Python (2) | 2024.07.04 |
---|---|
Baekjoon 1238. 파티 / Python (0) | 2024.07.04 |
Baekjoon 11779. 최소비용 구하기 2 / Python (0) | 2024.07.04 |
Baekjoon 1069. 집으로 / Pyhton (0) | 2024.07.04 |