접근

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

 

3020번: 개똥벌레

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

www.acmicpc.net

누적합을 이용해 높이 i 이상 석순의 개수, i 이상의 종유석의 개수를 저장해줍니다. 이 때, 종유석은 위서부터 아래로 내려온다는 점을 주의하여 풀어주면 문제를 해겷할 수 있습니다.

코드

import sys

input = sys.stdin.readline

N, H = map(int, input().split(" "))
down = [0] * (H + 1)
up = [0] * (H + 1)
min = N
num = 0

for i in range(N):
    if i % 2 == 0:
        down[int(input())] += 1
    else:
        up[int(input())] += 1
for i in range(H - 1, 0, -1):
    down[i] += down[i + 1]
    up[i] += up[i + 1]

for i in range(1, H + 1):
    if min > (down[i] + up[H - i + 1]):
        min = down[i] + up[H - i + 1]
        num = 1
    elif min == (down[i] + up[H - i + 1]):
        num += 1

print(min, num)

더 생각해 볼 것?

개인적으로 누적합 문제인지 모르고 풀었다면 엄청 헤메었을 것 같은 문제였습니다. 문제의 유형을 한가지 배웠습니다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!

반응형
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기