[BOJ 3020] 개똥벌레(Python)

문제

개똥벌레

---

문제 해설

종유석과 석순의 DP를 저장하는 리스트를 각각 만들어 해결한 문제입니다.

만약 길이가 5인 종유석이 3개고, 길이가 4인 종유석이 2개이면,
DP[4] = 3+2 입니다. 개똥벌레가 4보다 길이가 긴 종유석도 반드시 통과하기 때문입니다.

---

풀이 코드

import sys

input = sys.stdin.readline
n, h = map(int, input().rstrip().split())
up = [0] * (h + 1)
down = [0] * (h + 1)
answer = []

for i in range(1, n + 1):
    size = int(input())
    if i % 2 == 1:  # 석순(아래)
        down[size] += 1
    else:  # 종유석 (위)
        up[size] += 1

for i in range(h - 1, 0, -1):
    up[i] += up[i + 1]
    down[i] += down[i + 1]

# 파괴되는 종유석, 석순 검사
for section in range(1, h + 1):
    # 1 ~ h번째 구간까지 존재.
    # 구간당 개똥벌레가 -0.5에 있다고 인식
    answer.append(down[section] + up[h + 1 - section])

tot = 0
m = min(answer)
for i in answer:
    if i == m:
        tot += 1
print("{0} {1}".format(m, tot))

---