[Prefix Sum] 백준 3020번 “개똥벌레” Python 풀이

문제 링크

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

풀이

• 누적 합(Prefix Sum) 문제입니다.
• 먼저, 전체 높이 만큼의 인덱스를 가지는 배열을 2개 생성한 뒤,
• 각 배열에 대해, 석순과 종유석의 높이에 맞는 인덱스에 1을 증가시키고,
• 인덱스를 역순으로 누적합을 계산합니다.
• 이는, 석순 또는 종유석을 기준으로한 높이에 따라 잘리는 개수를 의미합니다.
  • 각 장애물을 기준으로한 높이를 의미하기 때문에,
  • 석순의 높이가 1, 3, 5 로 이루어져있을 때, 1의 높이에서 잘리는 석순의 개수는 3이며,
  • 종유석의 높이가 5, 3, 1 로 이루어져있을 때, 1의 높이에서 잘리는 종유석의 개수는 3입니다.
• 결과적으로, 해당 누적합 배열을 통해, 각 장애물을 기준으로, 높이가 i일 때 잘리는 석순 또는 종유석의 개수를 알 수 있게 됩니다.
• 따라서, 이제 각 장애물을 기준으로한 높이가 아닌, 전체 기준에서의 높이 i에 따라, 잘리는 석순과 종유석의 개수를 확인하며, 최소값과 동일 구간의 수를 출력하면 됩니다.
  • 전체 기준에서, 높이가 i일 때 잘리는 석순의 개수는, 석순 누적 배열의 [i] 인덱스 값입니다.
  • 전체 기준에서, 높이가 i일 때 잘리는 종유석의 개수는, 종유석 누적 배열의 [전체 높이 - i + 1] 인덱스 값입니다.

코드

import sys

# 장애물의 개수와 전체 높이
n, h = map(int, sys.stdin.readline().split())

# 석순 정보 저장
down = [0] * (h+1)
# 종유석 정보 저장
up = [0] * (h+1)

# 장애물의 크기 입력
for i in range(n):

    height = int(sys.stdin.readline())

    if (i % 2 == 0):
        # 석순의 높이에 따라 1 증가
        down[height] += 1
    else:
        # 종유석의 높이에 따라 1 증가
        up[height] += 1

# 인덱스를 역순으로 누적합을 계산
for i in range(h-1, 0, -1):
    down[i] += down[i+1]
    up[i] += up[i+1]

# 최소로 잘리는 장애물의 개수
min_count = n

# 동일한 개수로 잘리는 높이의 수
same_height = 0

# 전체 높이 i 기준, 높이에 따라 잘리는 석순과 종유석의 개수 파악
for i in range(1, h+1):

    # 현재까지 최소로 잘린 개수보다 현재 높이에서 더 적은 수로 잘리는 경우
    if (min_count > down[i] + up[h - i + 1]):
        min_count = down[i] + up[h - i + 1]
        same_height = 1

    # 현재 높이에서 잘린 개수가 현재까지 최소로 잘린 개수와 동일하다면
    elif (min_count == down[i] + up[h - i + 1]):
        same_height += 1

print(min_count, same_height)