[백준 Python] 3020 개똥벌레

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

문제정리

동굴 길이 N , 높이 H

석순, 종유석 ( 아래, 위 ) 순서로 장애물의 길이가 입력된다.

임의의 높이로 일직선을 그을 때 만나는 장애물의 수가 가장 적은 높이를 출력

 

문제풀이

먼저 가장 쉽게 생각해보자

모든 H 에 대해서 arr[N] 를 처음부터 끝까지 확인해서 석순은 H 보다 낮은 원소의 개수를, 종유석은 H 보다 높은 원소의 개수를 구하면 된다. 즉 시간은 모든 H 에 관해 arr[N] 배열의 확인을 하면 되므로 O(NH) 이다.

이 방법은 20만*40만이라 시간초과가 난다. 어떻게 줄일 수 있을 지 확인해보자

모든 H 에 관해 판단을 해야하는 것은 당연하다. -> 그래야 최소로 부딪히는 H 를 구하쥬

그렇다면 반복적으로 arr[N] 배열을 확인 하는 것을 줄여야 한다.

 

우리가 H 마다 계산하는 H 보다 작은 arr[N] 원소의 개수를 미리 bottom[H] 에 구해놓으면 된다.

bottom[7] = arr[7]

bottom[6] = bottom[7] + arr[6]

...

bottom[1] = bottom[2] + arr[1]

 

 

이를 종유석, 석순에 대해 짜주면

import sys
input = sys.stdin.readline
from collections import Counter

N, H = map(int, input().split())

top = [0] * (H + 1) # 종유석 
bottom = [0] * (H + 1) # 석순

for i in range(N):
   num = int(input())
   if i % 2 == 0: # 짝수, 아래, 석순
     bottom[num] += 1
   else:
     top[num] += 1

Px, Py = [0]* (H + 1), [0] * (H + 1)
Px[H], Py[1] = top[H], bottom[H]

for r in range(1,H):
    Px[H-r] = Px[H-r+1] + top[H-r]
    Py[r+1] = Py[r] + bottom[H-r]

P = [ 0 for _ in range(H)] 
for r in range(H):
   P[r] = Px[r+1] + Py[r+1]

c = Counter(P)
minXY = list(sorted(c.keys()))[0]
print(minXY, c[minXY])

 

참고 : https://deveun.tistory.com/entry/Python%EB%B0%B1%EC%A4%80-3020%EA%B0%9C%EB%98%A5%EB%B2%8C%EB%A0%88