[백준] 3020번 : 개똥벌레

문제

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

풀이

[백준] 3020번 : 개똥벌레 🥇(골드 5)
🎯 44.328%
⏰ 걸린 시간 : 68분
⏲ 시간복잡도
구간 합 O(n)

• 알고리즘 유형 : [구간 합]

📚 [구간 합]

✅ 풀이방법 & 구간 합 알고리즘로 푼 이유?
0. 구간 합을 먼저 구해놓는게 관건이다.
1. N^2으로 구해버리면 시간초과가 발생하기 때문이다.
2. 구간합을 쓰지않고 그때마다 결과를 탐색하게 하면 시간초과가 발생한다.

코드(code)

import sys
input = sys.stdin.readline
# N : 동굴의 길이 H: 동굴의 높이
N, H = map(int,input().split())
heights = [0]*(H+1)
flag = True
bottom = [0]*(H+1) #아래서 자라는놈 
top = [0]*(H+1) # 위에서 자라는놈 
for i in range(N):
    a= int(input())
    if flag== True:
        bottom[a] +=1
        flag=False
    else:
        top[H+1-a] +=1
        flag=True

start=False
for i in range(H-1,0,-1):
    bottom[i] +=bottom[i+1]
for i in range(1,H+1):
    if top[i] !=0: 
        start=True
    if start:
        top[i] +=top [i-1]
for i in range(H+1):
    heights[i]= bottom[i]+top[i]
heights.pop(0)

mini=min(heights)
count=heights.count(mini)

print(mini, count)

회고

2차원 배열에서 접근하는건 조금 까다로웠다 오답하면서 학습할 것.

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/Prefix_Sum/3020(%EA%B0%9C%EB%98%A5%EB%B2%8C%EB%A0%88).py