[백준/Python] BOJ 3020 - 개똥벌레

👀 문제

3020번: 개똥벌레 ✨ 골드 5

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

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

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

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

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

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

🔑 키포인트

누적합

⛑️ 2차원 배열 이용: 메모리 초과

처음에 2차원 배열을 사용해 문제를 풀려고 했다. 장애물이 있는 곳은 1로 바꾸어, 각 행마다 1의 개수를 세어 가장 작은 값과 같은 값을 가진 구간의 개수를 출력하도록 코드를 짰다. 코드는 제대로 작동했지만 백준에 제출하니 메모리 초과라는 결과가 나왔다.

### 메모리 초과
import sys
input = sys.stdin.readline

cave = [[0]*N for _ in range(H)]

# 장애물 세우기
for i in range(N):
    block = int(input())
    if i % 2 == 0:
        for j in range(block):
            cave[j][i] = 1
    else:
        for j in range(H-1, H-block-1, -1):
            cave[j][i] = 1

answer_arr = [] # 각 칸마다 파괴해야 하는 장애물 개수 배열
answer = 0 # 파괴해야 하는 장애물의 최솟값
count = 0 # 그러한 구간의 수

# 각 행마다 1의 개수 세기 (부숴야 하는 장애물)
for i in range(H):
    cnt = 0
    for j in range(N):
        if cave[i][j] == 1:
            cnt += 1
    answer_arr.append(cnt)

answer = min(answer_arr)

# 구간 수 세기
for ans in answer_arr:
    if ans == answer:
        count += 1

print(answer, count)

✍️ 성공 코드: 누적합 이용

1. 종유석과 석순 배열을 각각 만들어서 각 높이의 인덱스에 +1을 해 준다.
2. 누적합을 이용해 뒤에서부터 더한다 -> 길이가 긴 것부터 더해 줌
   높이 5, 3, 1의 종유석이 있다고 가정했을 때 맨 윗구간을 지나게 되면 종유석이 세 개 파괴되고 높이 1, 3, 5의 석순이 있다고 가정했을 때 첫 번째 구간을 지나면 석순이 세 개 파괴된다.
3. 석순의 앞부터, 종유석의 뒤부터 더해 주며 최솟값을 찾는다.
4. 같은 최솟값을 가진 구간의 수를 센다.

import sys
input = sys.stdin.readline

N, H = map(int, input().split())
top = [0] * (H+1) # 종유석
bottom = [0] * (H+1) # 석순
result = []
count = 0 # 구간 개수
min_count = N # 최소 장애물 개수

for i in range(N):
    # 석순
    if i % 2 == 0:
        bottom[int(input())] += 1
    # 종유석
    else:
        top[int(input())] += 1

# 거꾸로 계산 (누적합)
for i in range(H-1, 0, -1):
    bottom[i] += bottom[i+1]
    top[i] += top[i+1]

# 장애물 최솟값 찾기
for i in range(1, H+1):
    hap = bottom[i]+top[-i]
    result.append(hap)
    if min_count > hap:
        min_count = hap

# 같은 구간의 수 세기
for i in range(H):
    if result[i] == min_count:
        count += 1

print(min_count, count)