[python] 백준 3020번: 개똥벌레

 

 

 

 

 

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

난이도: 골드5

---

문제

---

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

 

출력

---

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

 

예제 입력

6 7
1
5
3
3
5
1

예제 출력

2 3

풀이

---

누적합 문제이다.

이분탐색으로도 해결할 수 있지만, 범위가 크지않아 단순하게 누적합으로 풀었다.

홀수,짝수번째 기둥이 서로 위,아래에서 오르므로 따로따로 누적합을 계산해 준 뒤,

인덱스를 뒤집어 하나로 합쳐준 뒤 최솟값을 찾아준다.

 

※ 주의사항

제출코드

import sys
input=sys.stdin.readline
N,H=map(int,input().split())
dp1=[0]*(H+1)
dp2=[0]*(H+1)
for i in range(N):
    h=int(input())
    if i%2:
        dp1[h]+=1
    else:
        dp2[h]+=1
tmp1,tmp2=[0]*(H+1),[0]*(H+1)
for i in range(H-1,0,-1):
    tmp1[i]+=dp1[i]+tmp1[i+1]
    tmp2[i]+=dp2[i]+tmp2[i+1]

res=[10**9,0]
for i in range(1,H+1):
    now=tmp1[i]+tmp2[H-i+1]
    if now<res[0]:
        res=[now,1]
    elif now==res[0]:
        res[1]+=1
print(*res)

 

---

틀린 부분이 있거나 인용한 부분에 대해 문제가 있을 시
댓글로 알려주시면 감사하겠습니다.