[JAVA] 백준 3020 개똥벌레

문제링크 : https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

이해가 안되서 이것저것 찾아보며 간신히 이해한 문제입니다.

 

1. 석순(아래), 종유석(위) 두개로 나누어서 배열 만들기
2. 높이별로 카운트를 높여서 누적합 구하기
3. 누적합 한 배열은 인덱스에서 벽을 몇개 부셔야하는지 나타냄

 

문제풀이 초기 설정을 위와 같이 잡고 문제를 풀었습니다.

석순 = down, 종유석 = up 배열입니다.

up 배열은 인덱스가 반대입니다. 그림으로 설명드리겠습니다.

 

 

1번 예제의 그림입니다. 파란색 숫자는 up배열의 인덱스를 나타냅니다.

높이별로 카운트하여 배열을 입력하면 다음과 같습니다.

총 3개의 석순 중 높이 1, 3, 5 가 하나씩 있으므로 down배열은 위와 같이 됩니다. 

총 3개의 종유석 중 높이 1, 3, 5가 하나씩 있으므로 up 배열은 위와 같이 됩니다. 

 

누적합을 구해보겠습니다.

 

 

down[1] 은 높이 1로 날았을 때 부딪히는 석순의 갯수를 나타냅니다.

up[1]은 높이 7로 날았을 때 부딪히는 석순의 갯수를 나타냅니다.

2 -> 6, 3 -> 5 순으로 진행됩니다. 파란 숫자와 검은색 숫자를 비교해 보시면 편합니다.

 

높이 1로 날았을때 부딪히는 총 장애물의 총 갯수는 down[1] + up[7]입니다.

 

이를 일반식으로 나타내면

i번째 높이 = down[i] + up[H-i+1] 이 됩니다.

 

전체 코드입니다.

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

public class Main {
    static int N, H;
    static int[] down, up;

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        // 인덱스 오류를 피하기 위해 +2
        down = new int[H + 2];
        up = new int[H + 2];

        for (int i = 0; i < N / 2; i++) {
            down[Integer.parseInt(br.readLine())]++;
            up[Integer.parseInt(br.readLine())]++;
        }

        for (int i = H; i > 0; i--) {
            down[i] += down[i + 1];
            up[i] += up[i + 1];
        }

        // 최솟값
        int min = N;
        // 횟수
        int cnt = 0;

        for (int i = 1; i <= H; i++) {
            // up의 인덱스는 임의로 설정한거라 실제 연산할때는 역순으로 바꿔줘야함
            // i:1 -> up:7, i:2 -> up:6
            int temp = down[i] + up[H - i + 1];
            if (temp < min) {
                min = temp;
                cnt = 1;
            } else if (temp == min) {
                cnt++;
            }
        }
        System.out.println(min + " " + cnt);
    }
}

 

많이 부족한 코드입니다. 수정할 점, 잘못된 점, 개선점 보이면 말씀해주세요!!

감사합니다.