백준 3020번 - 개똥벌레 / Python

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

3020번: 개똥벌레

문제 설명

문제

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

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟 개다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

---

정답

import sys

input = sys.stdin.readline

n, h = map(int, input().split())  # 길이, 높이

# 길이 별 장애물 저장
high = [0] * h  # 종유석
low = [0] * h  # 석순

# 종유석, 석순 입력 받기
for j in range(n // 2):
    i = int(input())
    high[i - 1] += 1
    i = int(input())
    low[h - i] += 1
if n % 2 == 1:
    i = int(input())
    low[h - i] += 1

# 종유석은 역순으로 누적 합, 석순은 정방향 누적 합 계산
for i in range(1, h):
    high[h - i - 1] += high[h - i]
    low[i] += low[i - 1]

# 두 배열을 합치면 경로 별 장애물 개수가 나옴
answer = [high[i] + low[i] for i in range(h)]

# 최솟값 및 개수 구하기
min = 200001
count = -1
for idx in range(len(answer)):
    if answer[idx] < min:
        min = answer[idx]
        count = 1
    elif answer[idx] == min:
        count += 1

print(min, count)

---

풀이

 앞에서 배운 누적 합을 응용하여 푸는 문제입니다. 

 

 배열로 동굴 전체의 2차원 지도를 만들어서 해결할 수 있으나, 이 방법을 이용하면 시간 초과가 생깁니다. 장애물을 입력하는데만 최대 200,000 *  200,000 = 400억번을 반복하게 됩니다. 

 

 이를 해결하기 위해서 누적 합을 어떻게 이용할 수 있을까 고민한 결과 종유석, 석순의 길이 별 개수를 센 뒤 이를 이용하여 누적합을 구하는 방식을 이용하였습니다. 길이 별로 입력을 받아서 석순은 순서대로 누적합을 구하고, 종유석은 역순으로 누적합을 구한 뒤 합치면 높이 별 장애물의 수를 구할 수 있습니다.