[Unsolved][JAVA] 백준 3020 개똥벌레

https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

1. 서론

 

풀이법이 바로 생각났지만 골드 문제이기 때문에 아니라고 생각이 들면서도 일단은 그렇게 풀었는데 '메모리 초과'로 틀렸다.

쉬워 보이지만 제약 조건 때문에 절대로 쉽게 풀 수 없는 문제이다. (당연함. 골드임.)

 

그래서 풀고 나서 구글링을 했더니 이런 글이 나왔다.

https://velog.io/@yule_gpark/백준-3020-개똥벌레-by-누적합-Python

[백준] 3020 개똥벌레 by 누적합 (Python)

그냥 이차원 배열로 풀기 => '메모리 초과'

직접 비교 => '시간 초과'

 

그래서 시간복잡도가 O(n)인 누적합으로 문제를 풀 수 있다고 한다.

 

2. 문제 풀이

 

석순: 아래에 있는 장애물

종유석: 위에 있는 장애물

 

이를 가로질러 지나갈 때 장애물을 뚫고 지나가야 하는데 그 값이 최소인 것을 구하고, 그게 몇 개가 있는지를 구하는 문제이다.

위에서 적었다시피 이 문제는 이차원 배열로 풀면 메모리 초과가 난다. 실제로 몸소 겪었고 그 사유는 n, h의 범위가 크기 때문이다.

 

그렇다면 무슨 원리로 이 문제가 누적합인 걸까? 처음엔 그 말 뜻을 이해하지 못해서 블로그를 세네 군데 들렸는데 이 블로그가 가장 이해하기 좋게 설명해 줬다.

 

https://baebalja.tistory.com/451

[백준 3020번 / C++ / 누적합] 개똥벌레

석순을 기준으로 보자면 길이가 1인 경우는 1~h의 범위중 뒤의 h부터 1의 방향으로 길이가 1이라는 의미이다.

이 길이가 1인 것이 5개가 있다고 가정한다면 h번째 칸을 지나갈 때 5개의 벽을 지나쳐야 한다는 뜻이다.

그럼 길이가 1, 2, 3, 4인 석순이 4개 있다고 가정하고 h번째 칸을 지나간다고 가정하면 뚫어야 하는 벽이 4개 있는 것이다.

h-1이면 3개, h-2칸이면 2개가 되는 식이다.

=> 바로 이 부분이 누적합의 개념이다.

 

그 길이의 칸을 지나면 깨는 장애물의 수를 누적합으로 구할 수 있는 것이다.

그러기 위해서 입력을 받을 때 해당 길이의 장애물이 몇 개 있는지를 cnt 한다.

ex) a [1]++; // 길이가 1인 장애물 수 cnt

석순, 종유석 각각 따로 입력을 받는다. 그러고 나서 1부터 h까지 누적합을 구한다. 

이때 누적합이 각 칸을 지날 때 부셔야 하는 장애물의 수이다.

종유석은 1~h순으로 석순은 h~1 순으로 되어있으므로 이 순서대로 합을 구해서 1~h 중 어디가 가장 적은 벽을 뚫어야 하는지, 몇 개가 그에 해당되는지 구한다.

 

3. 코드 설명

 

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

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int h = Integer.parseInt(st.nextToken());

int[] top = new int [h + 1]; //1~h
    int[] bottom = new int[h + 1]; //1~h
    for (int i = 0; i < n; i+=2) {
      bottom[Integer.parseInt(br.readLine())]++; //석순
      top[Integer.parseInt(br.readLine())]++; //종유석
    }

    for (int i = h - 1; i >= 1; i--) { //큰 수 ~ 작은 수 쪽으로 누적합. 1인 부분이 가장 낮은 곳이기 떄문에 큰 수인 숫자는 당연히 그부분에 벽이 있으므로
      bottom[i] += bottom[i + 1];
      top[i] += top[i + 1];
    }

    int[] cnt = new int[h + 1];
    int min = Integer.MAX_VALUE, ans = 0;
    for (int i = 1; i <= h; i++) {
      cnt[i] = bottom[h - i + 1] + top[i];//cnt 배열에 위 아래 장애물들을 i번째 순서에 맞춰서 더해줌(위, 아래 장애물 합침)
      min = Math.min(min, cnt[i]); //그 중 최솟값
    }

    for (int i = 1; i <= h; i++)
      if (cnt[i] == min) ans++; //최솟값이 몇 개인지

    System.out.print(min + " " + ans);
  }
}

 

 

길이가 1인 곳이 낮은 곳이고 숫자가 커질수록 위로 가기 때문에 가장 낮은 곳에 당연히 장애물이 있으므로 (ex) 길이 4인경우, 1칸부터 4칸까지 전부 장애물 존재) 역순으로 더해 누적합을 만들고 석순은 아래, 종유석은 밑부터 시작하므로 1~h칸을 기준으로 합을 구해서 답을 도출한다.

 

이해도 한 번에 안 가서 여러 블로그 보고 나서야 깨달았는데 이 문제만 보고 이 방법을 떠올려야 한다니... 진짜 쉽지 않다. ㅎ

누적합 문제는 대놓고 누적합을 구하라고 하지 않는 이상 많이 안 풀어봐서 유형이 익숙지 않다... ㅠㅠ