알고리즘 - Python / 백준 - 3020번 : 개똥벌레

3020번: 개똥벌레 (acmicpc.net)

3020번: 개똥벌레

 

---

풀이

• 동굴에 종유석과 석순이 있고 개똥벌레가 날아갈 때 , 부수는 종유석과 석순 개수의 최솟값을 구하고 그러한 구간이 얼마나 있는지 구하는 문제이다.
• N,H의 범위가 2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000 이므로 , 한줄 한줄 따라가며 계산하면 시간초과가 날 것이다.
• 종유석의 길이가 4 라면 , 4 3 2 1 구간은 모두 부숴야할 종유석이 +1 되고 , 석순도 거꾸로 보면 같다.
• 따라서 종유석과 석순 리스트를 구분하고 각각을 길이에 대해 누적합을 계산한다.
• 이후 만들어진 두 누적합 리스트를 같은 구간들끼리 더해주어 최종 정답을 구해낸다.
• 아래의 그림은 개똥벌레 문제의 1번 예시의 누적합을 알아보기 위한 예시 그림이다.

 

백준 사이트의 예시 1번의 그림 / N=6 ,H=7, 장애물 길이 = 1 5 3 3 5 1 의 경우

 

import sys

n,h = map(int,sys.stdin.readline().split(" "))
side_even = [0] * h
side_odd = [0] * h
for i in range(0,n):
    k = int(sys.stdin.readline())
    if i % 2 == 0:
        side_even[k-1] += 1
    else:
        side_odd[k-1] += 1
for i in range(h-1,0,-1):
    side_odd[i-1] += side_odd[i]
    side_even[i-1] += side_even[i]

minn = 200001
ans = 0

for i in range(0,h):
    t = side_even[i] + side_odd[h - 1 - i]
    if t < minn:
        minn = t
        ans = 0
    if t == minn:
        ans += 1
print(minn , end=" ")
print(ans)

---