백준 3020 개똥벌레 파이썬

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

3020번: 개똥벌레

 

개똥벌레가 부딪히는 종유석과 석순의 최솟 값을 구해야 하는 문제입니다.

위에서 자라나는 종유석과 아래에서 자라나는 석순을 동시에 고려하니 문제를 풀기가 쉽지 않아서 먼저 상황을 간단하게 나타내 보았습니다. 석순은 무시하고 종유석만 자라나는 상황을 생각해 봅니다.

 

1, 3, 5의 높이의 석순이 있을 때 개똥벌레가 부딪히는 장애물의 개수는 다음과 같습니다.

 

높이가 5인 석순이 하나 자라나면  개똥벌레가 높이 0~5인 구간을 지나갈 때에 부딪히는 횟수가 하나 늘어나고  

높이가 3인 석순이 자라나면 높이 0~3인 구간을 지나갈 때에 부딪히는 횟수가 하나 늘어나게 됩니다.

이는 누적합과 배열로 다음과 같이 표현할 수 있게 됩니다.

 

 

위와 같은 방법으로 석순만이 자라날 때에 부딪히는 횟수와 구간을 알 수 있었습니다. 중요한 것은 높이이고, 석순이 1, 3, 5 순서가 아니라 5, 3, 1처럼 바뀌어도 상관 없다는 사실도 알 수 있습니다. 종유석이 자라날 때에도 위와 같은 방식으로 생각합니다.

 

그러나 종유석은 위에서부터 자라나기 때문에, 개똥벌레가 지나가는 높이가 천장에 가까울 수록 부딪히는 횟수가 늘어나게 됩니다.

 

종유석과 석순에 부딪히는 횟수를 각각 구했기 때문에 두 횟수를 더해서 개똥벌레가 동굴 속을 진행하면서 부딪히는 전체 횟수를 구할 수 있게 됩니다. 종유석과 석순이 번갈아 생각하면 복잡하기 때문에 석순을 먼저 계산한 뒤에 종유석을 계산하였습니다.

예시의 경우 다음 그림과 같이 최소 부딪히는 횟수는 2, 그러한 구간은 3개입니다.

석순은 suffix sum을, 종유석은 preffix을 사용하는 문제였습니다.

n,h=map(int,input().split())
top=[]
bot=[]
go=[0]*(h+1)
go2=[0]*(h+1)
go3=[0]*(h+1)
 
for i in range (n) :
  k=int(input())
  if i %2==0: bot.append(k)
  else : top.append(k)
 
#print(bot, top)
 
 
for i in range (len(bot)) :
  go[bot[i]]+=1
  go2[  h  - top[i]  + 1 ]+=1
#print(go )
#print(go2)
 
 
for i in range( len(go)-1, 1,-1) :
  #print(i, go[i], go[i-1])
  go[i-1]+=go[i] 
#print(go)
 
for i in range (1,len(go2)):
  go2[i]+=go2[i-1]
#print(go2)
 
for i in range (1, len(go2)) :
  go3[i]=go[i]+go2[i]
 
go3.pop(0)
min_go=min(go3)
ans=go3.count(min_go)
print(min_go, ans)