[BOJ] 3020 개똥벌레 - JAVA

1. 문제

3020번: 개똥벌레

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

---

2. 풀이

위의 그림처럼 풀었다. 석순, 종유석을 각각 따로 저장해서 누적합을 따로 구한다.

종유석은 위에서부터 내려오므로 석순[h]+종유석[H-h+1]을 합하면 해당 높이에서 몇 개의 장애물을 뚫어야하는지 알 수 있다.

이를 이용해서 최솟값과 그 개수를 구한 뒤 출력한다.

import java.io.*;
import java.util.*;

public class BOJ_3020_개똥벌레 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int H = Integer.parseInt(st.nextToken());

      int[] fromB = new int[H+1];
      int[] fromT = new int[H+1];

      boolean isB = true;
      int len;
      for (int i = 0; i < N; i++) {
         len = Integer.parseInt(in.readLine());
         if(isB) fromB[len]++;
         else fromT[len]++;
         isB = !isB;
      }

      for(int h=H-1;h>0;h--){
         fromB[h] += fromB[h+1];
         fromT[h] += fromT[h+1];
      }

      int min = 200001, cnt = 0;
      int tmp;
      for(int h=1;h<=H;h++){
         tmp = fromB[h] + fromT[H-h+1];
         if(tmp<min){
            min = tmp;
            cnt = 1;
         }else if(tmp==min) cnt++;
      }

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

---

3. 결과

석순과 종유석을 따로 저장하지 않고 같은 count배열에 for문을 이용해서 한 칸 한 칸 누적시키니 시간초과됐다.