백준 5912 Haybale Stacking 파이썬

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

5912번: Haybale Stacking

 

 

Haybale을 지시 대로 쌓은 뒤에 정렬했을 때 중간 값의 높이를 찾는 문제입니다.

먼저 지시가 들어올 때마다 그냥 쌓는 방법을 생각해 볼 수 있었습니다. 예시의 2~4 구간에 haybale을 쌓을 때 다음과 같이 쌓을 수 있습니다.

그런데 이런 경우에는 제한 조건에서 가장 큰 값인 100만 개의 haybale을 2만 5천번 쌓으라 할 때에 250억번의 연산이 필요하기 때문에 시간 초과가 발생하게 됩니다. 따라서 다른 방법을 사용해야 하는데, 2부터 4까지 같은 값이 더해지기 때문에 두 번째 방법은 다음과 같이 생각해 볼 수 있습니다.

 

 

쌓기 시작되는 인덱스인 2에 1을 더하고, 끝나는 인덱스의 +1 에 -1을 저장하고 누적합을 구해도 처음 방법과 같은 결과를 얻게 됩니다. 처음 방법은 N*K 번의 연산이 필요했지만 두 번째 방법은 K +N 번의 연산 만으로  haybale을 지시에 따라 쌓을 수 있었습니다. 이는 시간 제한을 통과할 수 있는 속도입니다.

 

따라서 입력을 받을 때 쌓기 시작하는 곳에는 +1, 끝나는 곳 인덱스 +1에 -1을 저장하여 둔 뒤에, 입력이 끝나고 나서 누적합을 구하는 방식으로 haybale을 쌓고, 그 중 높이의 중간에 해당하는 값을 출력하는 문제였습니다.

 

n,k=map(int,input().split())
h=[0]*(n+1)
ps=[0]*(n+1)
ans=0
for i in range (k) :
  a,b=map(int,input().split())
  h[a]+=1
  if b<n : h[b+1]-=1 
  #print(h)
 
s=0
for i in range (n+1):
  s+=h[i]
  ps[i]=s
#print(ps)
ps.sort()
#print(ps)
ans=ps[(n+1)//2]
print(ans)