백준 - 3020 개똥벌레 [누적합][이모스]

 

3020번: 개똥벌레

1. 문제 요약

장애물의 위치가 주어지고, 해당  장애물을 통과하는 최솟값과 그러한 구간의 수를 출력하라

 

2. 접근 방법

위와 같은 장애물이 있다고 했을 때, 아래서부터 장애물을 통과하는 수를 세어보면

3, 3, 2, 3 입니다.

이런 식으로 완전탐색으로도 충분히 정답은 구할 수 있습니다만, 시간과 메모리가 한정되어 있기 때문에 다른 방법으로 풀어야 합니다.

 

이모스법 알고리즘을 알고 있다면 쉽게 풀 수 있습니다.

 

위 그림과 같이 장애물이 시작되는 위치에 +1, 끝나는 위치에 -1을 해줍니다.

 

모두 표시를 해준 뒤, 각각 값을 계산합니다. (맨 위의 -1은 해당 문제에서 범위 밖이기 때문에 무시해 줍니다.)

계산된 값은 3, 0, -1, 1 입니다.

이를 순차적으로 누적합을 계산해 보면, 3, 3, 2, 3 입니다.

 

위에서 완전탐색으로 세어본 결과처럼 장애물을 통과한 수를 계산해 낼 수 있습니다.

이를 토대로 코드로 구현하면 됩니다.

 

3. 파이썬

from sys import stdin
input = stdin.readline

N, H = map(int, input().split())

arr = [0] * H
for i in range(0, N, 2):
    arr[0] += 1
    arr[int(input())] -= 1
    arr[H - int(input())] += 1

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

minimum = min(arr)
count = arr.count(minimum)

print(minimum, count)

 

4. 자바

int N = nextInt(br);
int H = nextInt(br);

int[] arr = new int[H];
for (int i = 0; i < N; i += 2) {
    arr[0] += 1;
    arr[nextInt(br)] -= 1;
    arr[H - nextInt(br)] += 1;
}

for (int i = 1; i < H; i++) {
    arr[i] += arr[i - 1];
}

int minimum = Integer.MAX_VALUE;
int count = 0;
for (int num : arr) {
    if (num < minimum) {
        minimum = num;
        count = 1;
    } else if (num == minimum) {
        count++;
    }
}

System.out.printf("%d %d", minimum, count);

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/3020.%E2%80%85%EA%B0%9C%EB%98%A5%EB%B2%8C%EB%A0%88