154. 개똥벌레

백준

1. Python

부분합

"""
author : Park Min Hyeok
github : https://github.com/m1nnh
e-mail : alsgur9784@naver.com

title : 개똥벌레
description : 부분합
"""

N, H = map(int, input().split())
Cave = [int(input()) for _ in range(N)]

A = [0] * (H + 2)
B = [0] * (H + 2)
result = [0] * (H + 2)


for i in range(N):
    h = Cave[i]
    if i % 2 == 0:
        B[h + 1] += 1
    else:
        A[H - h] += 1

for i in range(2, H + 1):
    B[i] += B[i - 1]

for i in range(H, -1, -1):
    A[i] += A[i + 1]


for i in range(1, H + 1):
    result[i] = A[i] + B[i]

print(N - max(result), result.count(max(result)))

참고

• 땅에서 천장 방향으로 높이를 1씩 증가하면서 부딪히는 갯수를 세게 되면

  1)석순의 경우, 석순의 높이보다 1 높아지는 지점에서 해당 석순에 부딪히지 않게되므로, 부딪히는 갯수가 1 줄어들게 됩니다.

  2) 종유석의 경우, h - 종유석의 길이보다 1 높아지는 지점에서 해당 종유석에 부딪히게 되므로, 부딪히는 갯수가 1 늘어나게 됩니다.

  3) 1) 속성을 이용하여 각 높이로 변경 될 때, 몇개의 장애물이 새로 부딪히는지, 덜 부딪히게 되는지를 배열에 저장합니다.

  4) 2)에서 구한 배열을 가지고, 0 ~ h까지 누적 합들을 구하면서, 최소로 부딪히는 값과 그 구간의 갯수를 구한다.

이진 탐색 + 정렬

참고

n, h = map(int, input().split())

down = []
up = []
for i in range(n):
    if i % 2 == 0:
        down.append(int(input()))
    else:
        up.append(int(input()))

down.sort()
up.sort()

min_count = n
range_count = 0


def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return start


for i in range(1, h + 1):
    down_count = len(down) - binary_search(down, i - 0.5, 0, len(down) - 1)
    top_count = len(up) - binary_search(up, h - i + 0.5, 0, len(up) - 1)

    if min_count == down_count + top_count:
        range_count += 1
    elif min_count > down_count + top_count: # 현재 범위가 새로운 최소 값이면
        range_count = 1
        min_count = down_count + top_count

print(min_count, range_count)

• 장애물이 설치된 동굴에 개똥벌레 한마리가 날라가는데 동굴의 높이가 6일 때, 개똥벌레가 날아가는 높이가 3이라고 한다면 아래에서부터 높이 2~3 (2.5라고 생각하면 쉽다) 구간을 날라간다.

  • 그래서 3보다 낮은 석순에는 모두 부딪히게 되고, 3보다 큰 종유석에는 모두 부딪히게 된다. ( 위에서 부터 4 만큼 내려온 종유석에는 아래에서 부터 2.5만큼 날아오른 개똥벌레가 부딪히기 때문)

  • 왜냐하면, 높이 6의 동굴에서 높이 2짜리 종유석은 높이 4 (실질적으로 3.5) 위로의 개똥벌레가 모두 부딪히기 때문이다.

• 개똥벌레가 파괴해야 하는 장애물의 최소 개수와 이 최소값이 나오는 구간의 수를 구하는 것이다.

  • 가장 먼저 떠오른 방법은 석순과 종유석의 배열을 따로 두고, 각각의 배열을 정렬 한 후에 처음 개똥벌레가 부딪히기 시작한 높이를 계산하는 방식이다. 왜냐하면 그 이후의 구간은 모두 부딪힌다는 이야기가 되기 때문에 첫 구간만을 구해 그 구간 전까지의 개수를 통해 답을 구할 수 있기 때문이다. 이러한 접근 방식을 누적 합(또는 구간합)이라고 하는데

• 석순과 종유석의 배열이 각각 정렬되어 있기 때문에, 배열의 중간지점에서 개똥벌레가 부딪히는지 테스트를 진행한다.

보통의 이진탐색 과정과 마찬가지로 start값과 end값에 변화를 주며 mid값을 조정하여 개똥벌레가 최소한으로 부딪히는 구간을 찾으면 된다.

2. C++

구간 트리

#include <cstdio>

int n, h, answer, count;
int sum[500010];

int main() {
    scanf("%d %d", &n, &h);
    for (int i = 0 ; i < n ; i++) {
        int bar;
        scanf("%d", &bar);
        if (i & 1) {
            // 종유석
            sum[h - bar + 1]++;
        }
        else {
            // 석순
            sum[1]++;
            sum[bar + 1]--;
        }
    }
    answer = -1;
    for (int i = 1 ; i <= h ; i++) {
        sum[i] += sum[i - 1];
        if (answer == -1 || sum[i] < answer) {
            answer = sum[i];
            count = 1;
        }
        else if (sum[i] == answer) {
            count++;
        }
    }

    printf("%d %d", answer, count);
}

시간 초과

#include <cstdio>

int n, h, answer, count;
int seok[200000], jong[200000];

// x구간으로 날아갈때 k번째 석순과 만나는지 
bool check_seok(int k, int x) {
    if (x <= seok[k]) return true;
    return false;
}

// x구간으로 날아갈때 k번째 종유석과 만나는지 
bool check_jong(int k, int x) {
    if (h - jong[k] + 1 <= x) return true;
    return false;
}

int fly(int x) {
    int res = 0;
    for (int i = 0 ; i < n ; i += 2) {
        // 석순과 만나는지
        if (check_seok(i, x)) res++; 
        // 종유석과 만나는지 
        if (check_jong(i, x)) res++;
    }
    return res;
}

int main() {
    scanf("%d %d", &n, &h);
    for (int i = 0 ; i < n ; i += 2) {
        scanf("%d", &seok[i]);
        scanf("%d", &jong[i]);
    }
    answer = -1;
    for (int i = 1 ; i <= h ; i++) {
        int crash = fly(i);
        if (answer == -1 || crash < answer) {
            answer = crash;
            count = 1;
        }
        else if (crash == answer) {
            count++;
        }
    }
    printf("%d %d", answer, count);
}