[Python][백준] 3020번 개똥벌레

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

공부 날짜 : 2023.01.25
정답 참조 여부 : O

석순과 종유석이 주어질 때 높이별로 장애물이 가장 적은 높이의 장애물 개수와 해당 장애물 개수로 지나갈 수 있는 높이의 개수를 구하는 문제이다.

---

처음에는 동굴 자체를 구현을 했다.

2차 배열을 구현해서 장애물이 있는 위치는 True, 없는 위치는 False로 구현해서
각 높이별로 장애물 개수와 최소 장애물의 개수를 구했는데 메모리 초과가 떴다.

메모리 단축을 위해 높이별로 장애물이 있는 칸을 +1을 처리 해줬는데 시간초과가 떴다....

도저히 이해가 되지 않아서 정답을 참조했는데

석순과 종유석을 구분하고 각 장애물의 높이만 기록해줬다.

맨 위에서 장애물은 동굴 길이의 절반만큼만 가지고(동굴 길이는 짝수로만 주어진다)

종유석을 만나면 개수만큼 +해주고, 석순이 없어지면 개수만큼 -를 해줬다.

그러면서 개수를 비교 해줬더니 정답으로 나왔다.

누적 합이라는게 어떤느낌인지 감을 잡을 수 있는 문제였다.

근데 이게 이분 탐색이라는데 왜 이분탐색인지는 전혀 모르겠다...

소스코드

import sys
input = sys.stdin.readline
##########################################
# n은 동굴 길이, h는 동굴 깊이
# n은 짝수
n, h = map(int, input().split())

# 종유석
up = [0 for _ in range(h)]
# 석순
down = [0 for _ in range(h)]

# 석순과 종유석을 입력받아서 높이 개수 세기
for i in range(n):
    # 석순이나 종유석의 크기를 나타내는 변수
    stone = int(input())

    # 석순
    if i % 2 == 0:
        down[h-stone] += 1

    # 종유석
    else:
        up[stone-1] += 1

min_value = n+1
min_count = 0

count = n//2

for i in range(h):
    count += down[i]

    if count < min_value:
        min_value = count
        min_count = 1
    elif count == min_value:
        min_count += 1

    count -= up[i]


print(min_value, min_count)