BOJ - 3020 개똥벌레

Problem

---

Solve

2차원 배열에 각 장애물을 선언하고 이중 for문으로 비교한다면 500000*200000으로 시간 초과가 발생한다.

y축에서 출발했을 때의 장애물을 각각 1차원 배열에 저장하여 같은 위치에서 중복되는 장애물의 개수를 구해 최소가 되는 장애물의 개수와 파괴해야하는 장애물 개수를 반환한다.

• 죽순 배열
  • 석순의 배치는 석순의 크기 위치에 +1
• 종유석 배열
  • 종유석의 배치는 뒤에서 부터 석순의 크기 위치에 +1

주어진 장애물이 {1,5,3,3,5,1} 일 때

석순과 종유석 배열에 각 높이에 있는 장애물을 배치한다.

석순 배열은 배열의 뒤에서 부터 합하여 0까지 겹쳐지는 장애물의 개수를 구한다.
종유석 배열은 배열의 앞에서부터 뒤까지 겹쳐지는 장애물의 개수를 구한다.

높이 1,3,5에서 파괴해야하는 장애물의 개수는 2개로 최소이고 이는 총 3개의 구간이 있다.

---

Code

public class 개똥벌레 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		int[] bottom = new int[H];
		int[] top = new int[H];

		//맨 앞의 장애물은 석순
		for (int i = 1; i <= N; i++) {
			int size = Integer.parseInt(br.readLine());
			if (i % 2 != 0) {
				bottom[size - 1] += 1;
			} else {
				top[(H - 1) - (size - 1)] += 1;
			}
		}

		int bottomSum = 0;
		int topSum = 0;
        //석순배열은 뒤에서부터 앞으로 합 구하기
        //종유석배열은 앞에서부터 뒤로 합 구하기
		for (int i = 0; i < H; i++) {
			bottomSum += bottom[H - 1 - i];
			bottom[H - 1 - i] = bottomSum;

			topSum += top[i];
			top[i] = topSum;
		}

		int min = Integer.MAX_VALUE;
		int count = 0;
        //장애물 최소값과 해당 구간 개수
		for (int i = 0; i < H; i++) {
			int sum = bottom[i] + top[i];

			if (sum < min) {
				count = 1;
				min = sum;
			}else if(sum == min){
				count++;
			}
		}

		StringBuilder sb = new StringBuilder();
		sb.append(min);
		sb.append(" ");
		sb.append(count);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference