[백준] 3020번: 개똥벌레

문제

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

풀이

누적합을 활용한 풀이

종류석: 바닥에서 자라나는 것, bottom
석순: 천장에서 자라나는 것, top

같은 높이의 종류석과 석순의 개수를 저장하는 배열 bottom, top을 만들어서
저장한다.

종류석은 홀수번째의 입력이고, 석순은 짝수번재의 입력이다.

이후 역순으로 누적합 배열을 구한다.
이 배열이 의미하는 것은 인덱스가 i 라고 가정하자
높이가 i 일때 깰 수 있는 종류석, 석순의 개수를 의미한다.

이후 개똥벌레가 모든 높이를 지나가면서 깨는 종류석 + 석순의 개수를 구한다.
만약 높이가 1이라면 종류석은 의 높이는 1, 석순의 높이는 7 이어야
해당 높이에서 종류석과 석순을 모두 깰 수 있다.

따라서 식은 다음과 같다.
break_on_height = bottom[i] + top[H - i + 1]

만약 이 값이 이전의 깨왔던 것보다 높이가 작다면 출력할 높이를 이 높이로 초기화하고
깨왔던 개수도 1로 초기화한다.

만약 이전의 깨왔던 것과 높이가 같다면 깬 개수를 1 증가 시킨다.

import sys

input = sys.stdin.readline

N, H = map(int, input().rstrip().split(" "))
bottom = [0] * (H + 1)
top = [0] * (H + 1)

for i in range(N):
    height = int(input())
    if i % 2 == 1:
        bottom[height] += 1
    else:
        top[height] += 1


def solution(N, H, bottom, top):
    for i in range(H - 1, 0, -1):
        bottom[i] = bottom[i] + bottom[i + 1]
        top[i] = top[i] + top[i + 1]

    min_height = N
    count = 0

    for i in range(1, H + 1):
        break_on_height = bottom[i] + top[H - i + 1]
       
        if min_height > break_on_height:
            min_height = break_on_height
            count = 1

        elif min_height == break_on_height:
            count += 1

    print(min_height, count)
    return


solution(N, H, bottom, top)