[Java] 백준 3020번 - 개똥벌레

• 문제
  • 링크 : https://www.acmicpc.net/problem/3020
  • 장애물 최소 개수와 구간 개수

 

• 조건
  • 2 ≤ N ≤ 200,000
  • 2 ≤ H ≤ 500,000
  • N은 항상 짝수
  • N, H, 종유석 또는 석순의 길이 모두 양수

 

• 입력
  • 첫번째 줄
    • N H : N - 동굴의 길이, H - 동굴의 높이
  • 두번째 줄 ~ N+1
    • 종유석 또는 석순의 길이( 1 ≤ 길이 < H)

 

• 출력
  • 장애물 최소 개수와 구간 개수

 

• 로직 1)
  • N x H를 하면 O(N^2)이므로 시간초과 발생
  • O(N) 구현 → 누적합 이용 

package backjoon;

import java.util.Arrays;
import java.util.Scanner;

public class No3020 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 넓이
        int H = sc.nextInt(); // 높이
        int[] arr = new int[H + 1]; // 구간 별 장애물 개수

        int[] bottom = new int[H]; // 석순 길이
        int[] floor = new int[H]; // 종유석 길이

        // 입력
        for (int i = 0; i < N / 2; i++) {
            int tmp = sc.nextInt();
            bottom[tmp]++;

            tmp = sc.nextInt();
            floor[tmp]++;
        }

        // edge 케이스
        arr[H-1] = bottom[H-1];
        arr[2] = floor[H-1];
        int tmp = 3;
        // 누적합으로 구간별 장애물 개수 구하기
        for(int i=H-2; i>=1; i--) {
            bottom[i] = bottom[i+1] + bottom[i];
            floor[i] = floor[i+1] + floor[i];

            arr[i] += bottom[i];
            arr[tmp] += floor[i];
            tmp++;
        }

        // 최소 장애물 개수와 구간 개수 구하기
        int index = 1;
        int min = arr[index];
        int count = 1;
        for (int i = 2; i <= H; i++) {
            if (min > arr[i]) {
                index = i;
                min = arr[i];
                count = 1;
            } else if (min == arr[i]) {
                count++;
            }
        }

        System.out.println(min + " " + count);
    }
}

 

• 결과
  • 성공