[백준 3020번] 개똥벌레 (java)

3020번: 개똥벌레

 

누적합으로 문제를 해결하였다.

 

각각의 높이에 따라 석순과 종유석의 개수를 카운트하는 두 개의 배열 bot, top을 생성하였다.

 

예를 들어, 첫 번째 구간에서는 석순이 7개 존재하므로 bot[1] = 7 이 된다.

두 번째 구간에는 석순이 6개 존재하므로 bot[2] = 6 

세 번째 구간에는 석순이 5개 존재하므로 bot[3] = 5 

네 번째 구간에는 석순이 1개 존재하므로 bot[4] = 1 

다섯 번째 구간에는 석순이 0개 존재하므로 bot[5] = 0 

 

첫 번째 구간에는 종유석이 0개 존재하므로 top[1] = 0

두 번째 구간에는 종유석이 2개 존재하므로 top[2] = 2

세 번째 구간에는 종유석이 5개 존재하므로 top[3] = 5

네 번째 구간에는 종유석이 7개 존재하므로 top[4] = 7

다섯 번째 구간에는 종유석이 7개 존재하므로 top[5] = 7

		for (int i = 0; i < N / 2; i++) {
			bot[Integer.parseInt(br.readLine())]++;
			top[H - Integer.parseInt(br.readLine()) + 1]++;
		}

 

그 다음, 구해진 bot과 top 배열을 이용하여 누적합(Prefix Sum)을 구한다.

누적합을 이용하면 O(n)의 시간복잡도가 걸린다.

		for (int i = 1; i <= H; i++) {
			bot[i] += bot[i - 1];
		}

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

 

누적합을 구한 후, 첫 번째 구간부터 H번째 구간까지 차례대로 장애물의 수를 확인한 다음, min과 cnt을 갱신해준다.

 

i번째 구간에서의 석순의 개수는 bot[H] - bot[i-1]

i번째 구간에서의 종유석의 개수는 top[H] - top[i+1] 로 구할 수 있다.

이 두 결과를 더한 값이 i번째 구간에서의 장애물의 총 개수가 된다.

int obs = (bot[H] - bot[i - 1]) + (top[1] - top[i + 1]);

		int min = N;
		int cnt = 0;

		for (int i = 1; i <= H; i++) {
			int obs = (bot[H] - bot[i - 1]) + (top[1] - top[i + 1]);

			if (obs < min) {
				min = obs;
				cnt = 1;
			} else if (obs == min)
				cnt++;
		}

 

전체 코드 :