[BOJ/JAVA] 3020번: 개똥벌레

3020번: 개똥벌레

3020번: 개똥벌레

키워드

첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

---

구현

동굴의 총 높이는 H이다.

height 높이로 날아갈 때 부딪히는 석순의 수와, 종유석의 수를 저장을 한다.

석순[], 종유석[]

석순의 길이가 A 일 때 [A] 높이 까지 부딪히는 석순이 존재한다면 석순[A] += 1 연산을 한다.

종유석의 길이가 B 일 때 [H-B+1] 높이 부터 부딪히는 종유석이 존재한다면 종유석[H-B+1] += 1 연산을 한다.

1. 부딪히는 석순의 수 구하기
2. 직전 석순의 데이터를 누적합으로 저장하기 위하여, [A] 높이에서 부딪힌다면 A 이하의 높이에서 전 부 부딪히므로, 높이의 역순으로 돌면서 누적합을 처리한다. 단, A 이하의 어떤 지점 K에서 저장된 값이 추가적으로 있으므로 석순[K] += 석순[K+1] 연산을 한다.
3. 부딪히는 종유석의 수 구하기
4. 직전 종유석의 데이터를 누적합으로 저장하기 위하여, [B] 높이에서 부딪힌다면 B 이상의 높이에서 전부 부딪히므로, 높이의 오름차순으로 돌면서 누적합을 처리한다. 단 B 이상의 어떤 지점 K에서 저장된 값이 추가적으로 있을 수 있으므로 종유석[K+1] += 종유석[K] 연산을 한다.
5. 석순의 수 + 종유석의 수 구하기이제 height를 1부터 H까지 돌면서 최솟값과 그 최솟값의 수를 찾는다.
6. 앞서 [height] 높이로 날아갈 때 부딪히는 석순의 수와, 종유석의 수를 구했다.

---

코드

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

public class java_3020 {
    static int N, H;

    static int cave[];
    // [H][0] 이하는 무조건 부딪힌다.
    // [H][1] 이상은 무조건 부딪힌다.
    static int caveEscape[][];

    // 높이가 H일 때 부숴야 하는 갯수
    static int breakList[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 동굴의 길이 N 미터(N 짝수)
        // 동굴의 높이 H 미터

        // 첫 번째 장애물은 항상 석순
        // 종유석 석순 반복

        //

        // [i] 높이에 있을 때 피해야하는 종유석의 수, 석순의 수 저장하기
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        cave = new int[N];
        caveEscape = new int[H][2];

        for (int i = 0; i < N; i++) {
            cave[i] = Integer.parseInt(br.readLine());

            // 석순의 경우
            if (i % 2 == 0) {
                caveEscape[cave[i] - 1][0] += 1;
            }
            // 종유석의 경우
            else {
                caveEscape[H - cave[i]][1] += 1;
            }

        }

        // 석순은 역방향으로 더해주기
        for (int i = H - 1; i > 0; i--) {
            caveEscape[i - 1][0] += caveEscape[i][0];
        }

        // 종유석은 정방향으로 더해주기
        for (int i = 1; i < H; i++) {
            caveEscape[i][1] += caveEscape[i - 1][1];
        }

        // 두개의 합
        breakList = new int[H];

        for (int i = 0; i < H; i++) {
            breakList[i] = caveEscape[i][0] + caveEscape[i][1];
        }

        // 최솟값과 최솟값의 갯수 찾기
        int minValue = breakList[0];
        int minCount = 1;
        for (int i = 1; i < H; i++) {
            if (breakList[i] < minValue) {
                minCount = 1;
                minValue = breakList[i];
            } else if (breakList[i] == minValue) {
                minCount++;
            }
        }

        System.out.println(minValue + " " + minCount);

        br.close();
    }
}

---