자바 [Algorithm] 누적합 - 백준 3020 개똥벌레

1. 문제

 

 

2. 접근법

1. 홀수번째는 석순, 짝수번째는 종유석이 입력된다.

2. 석순과 종유석 배열에 대한 누적합을 계산하여 높이 i번째까지 석순과 종유석의 개수를 저장한다.

3. 부딪히는 장애물 수를 계산한다.

int[] arr = new int[H+1];

for (int i = 1; i < H+1; i++) {
    arr[i] += odd[H] - odd[i-1];
    arr[i] += even[H] - even[H-i];
    min = Math.min(arr[i], min);
}

4. 최소 높이의 개수를 계산한다.

 

3. 코드

package week08;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baek3020 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        int H = Integer.parseInt(stringTokenizer.nextToken());

        int[] odd = new int[H+1]; //석순
        int[] even = new int[H+1]; //종유석
        int result = 0;
        int min = Integer.MAX_VALUE;

        for (int i = 1; i < N+1; i++) {
            int a = Integer.parseInt(bufferedReader.readLine());

            if(i % 2 != 0){
                odd[a]++;
            }else{
                even[a]++;
            }
        }

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

        int[] arr = new int[H+1];

        for (int i = 1; i < H+1; i++) {
            arr[i] += odd[H] - odd[i-1];
            arr[i] += even[H] - even[H-i];
            min = Math.min(arr[i],min);
        }

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

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