[BAEKJOON_3020 - JAVA] 개똥벌레

문제

www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

 

풀이

• BruteForce로 풀려다 시간 제한 1sec를 본뒤 고민. 이분탐색을 사용하는 것 까지는 알겠는데 적용방법을 블로그를 통해 참고. 누적합을 적용해야하는 것을 참고했다.
• 석순과 종유석을 분리하는 이분 탐색으로, 누적합을 통해 파괴하지 않는 장애물을 제외.
• 석순의 경우 바닥, 종유석의 경우 천장임을 주의하며 풀이.

 

 

과정

1. 석순과 종유석이 순서대로 들어오므로, 입력을 각각 다른 배열에 높이를 기준으로 받는다.
2. 높이에 따른 배열들을 활용 이번에도 석순과 종유석 각각 누적합의 배열을 만든다.
   ex) 석순의 경우, 높이가 4로 날아갔을때 높이가 4보다 작은 석순들은 파괴되지 않으므로 제외 시켜주어야한다.
   → 누적합을 구하는 이유
3. 반복문을 동굴의 길이가 아닌 높이로 설정.
   기존에 석순과 종유석의 길이로 배열을 받았기 때문이다.
4. 높이 i로 비행할 때, bot의 경우 부딪히는 석순 = 전체 석순의 개수 - (i-1) 이하인 석순의 갯수
5. 높이 i로 비행할 때, top의 경우 부딪히는 종유석  = 전체 종유석의 갯수 - (H-i) 이하인 종유석의 개수

 

 

알고리즘 지식

• 이분 탐색
• 누적합

 

 

JAVA코드

package BaekJoon_2020_12_22__23;

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

/**
 * @packageName : BaekJoon_2020_12_22__23
 * @fileName : BJ_3020_개똥벌레.java
 * @author : Mingeon
 * @date : 2020. 12. 23.
 * @language : JAVA
 * @classification :
 * @time_limit : 19:41 ~ 20:38
 * @required_time : 1sec
 * @submissions : 1
 * @description
 */

public class BJ_3020_개똥벌레 {

	static int N; // 동굴의 길이
	static int H; // 동굴의 높이
	static int[] top;// 석순
	static int[] bot;// 종유석
	static int min; // 파괴하는 장애물의 최솟값
	static int cnt; // min에 해당되는 구간의 수

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 동굴의 길이
		H = Integer.parseInt(st.nextToken()); // 동굴의 높이
		bot = new int[H + 1]; // 석순 정보
		top = new int[H + 1]; // 종유석 정보
		min = N; // 파괴하는 장애물의 최솟값
		cnt = 0; // min에 해당되는 구간의 수

		for (int i = 0; i < N / 2; i++) {
			bot[Integer.parseInt(br.readLine())]++; // 석순(bot)
			top[Integer.parseInt(br.readLine())]++; // 종유석(top)
		} // End of input

		process();

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

	}

	private static void process() {

		int[] bot_sum = new int[H + 1]; // 높이가 h이하인 석순의 갯수
		int[] top_sum = new int[H + 1]; // 높이가 h이하인 종유석의 갯수

		// 누적합 계산
		for (int i = 1; i < H + 1; i++) {
			top_sum[i] = top_sum[i - 1] + top[i];
			bot_sum[i] = bot_sum[i - 1] + bot[i];
		}

		for (int i = 1; i < H + 1; i++) {
			int crush = 0; // 부딪히는 개수

			// 부딪히는 석순의 갯수 = 전체 석순의 갯수 - (h-i)이하인 석순의 갯수
			crush += bot_sum[H] - bot_sum[i - 1];
			// 부딪히는 종유석의 갯수 = 전체 종유석갯수 - (i-1)이하인 종유석의 갯수
			crush += top_sum[H] - top_sum[H - i];

			// 최솟값 && 개수 위한 조건문
			if (min > crush) {
				min = crush;
				cnt = 1;
			} else if (min == crush) {
				cnt++;
			}
		}

	}

}