[Java] 백준 3020번 개똥벌레

누적합 문제입니다.

개똥벌레가 직선으로 이동할 때 파괴해야 하는 장애물의 최솟값과 그러한 구간의 개수를 구해야합니다.
장애물은 높이가 주어지고 아래, 위, 아래, 위 ... 아래, 위 순서로 설치됩니다.

먼저 위 아래를 구분해서 배열을 만들어주었습니다.
그리고 각 높이의 개수를 구해줍니다.

그렇다면 예를들어 아래와 같은 배열이 만들어집니다.
위 3미터 2개
위 2미터 3개
위 1미터 1개

아래 3미터 1개
아래 2미터 2개
아래 1미터 2개

위처럼 만들어졌다고 가정하면 누적합을 사용해서 값을 더해줍니다.
3미터인 경우 2미터도 포함이므로 3미터를 2미터에 더해줍니다.
더해진 2미터를 1미터에 더해줍니다.

누적합 배열이 만들어졌습니다.
위 3미터 2개
위 2미터 5개
위 1미터 6개

아래 3미터 1개
아래 3미터 3개
아래 1미터 5개

누적합 배열을 바탕으로 결과 배열을 만들어냅니다.

for (int i = 1; i < m; ++i) {
  result[i] += arr1[i];
  result[m + 1 - i] += arr2[i];
}

구해진 결과 배열로 가장 적은 개수와 구간의 수를 구해서 출력해주었습니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int[] arr1 = new int[m]; 
    int[] arr2 = new int[m]; 
    int[] result = new int[m + 1];
    int minNum = 987654321;
    int cnt = 0;

    for (int i = 0; i < n; ++i) {
      int num = Integer.parseInt(br.readLine());
      if (i % 2 == 0) {
        ++arr1[num];
      } else {
        ++arr2[num];
      }
    }

    for (int i = m - 1; i > 0; --i) {
      arr1[i - 1] += arr1[i];
      arr2[i - 1] += arr2[i];
    }
    
    for (int i = 1; i < m; ++i) {
      result[i] += arr1[i];
      result[m + 1 - i] += arr2[i];
    }

    for (int i = 1; i <= m; ++i) {
      if (minNum > result[i]) {
        minNum = result[i];
        cnt = 1;
      } else if (minNum == result[i]) {
        ++cnt;
      }
    }
    
    bw.write(minNum + " " + cnt);
    bw.close();
  }
}