아이디어

• 석순에 대해서 먼저 생각해보자.
• 바닥부터 $i$번째 구간까지 뻗어있는 석순의 개수를 d[i]라 하면 개똥벌레가 $i$번째 구간으로 날고 있을 때 부숴야 하는 석순 개수는 d[N] + d[N-1] + ... + d[i]다.
• 마찬가지로 천장부터 $i$번째 구간까지 뻗어있는 종유석의 개수를 u[i]라 하자. 부숴야하는 종유석의 개수는 u[1] + u[2] + ... + u[i]이다.
• 이는 누적합이므로 미리 구하면 계산량을 줄일 수 있다.
  • U[i] = u[1] + u[2] + ... + u[N]는 U[i] = U[i-1] + u[i]와 같이 계산할 수 있다.
  • 마찬가지로 D[i] = d[N] + d[N-1] + ... + d[i]는 D[i] = D[i+1] + d[i]와 같이 계산할 수 있다.
• 개똥벌레가 $i$번째 구간을 날 때 부수는 장애물 수는 U[i] + D[i]다.
• $1 \le i \le N$의 모든 $i$에 대해 U[i] + D[i]의 최솟값과 그 최솟값이 등장한 횟수가 답이 된다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, H, min, cnt;
	static int[] u, d, U, D;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		H = Integer.parseInt(tk.nextToken());

		u = new int[H+1];
		d = new int[H+1];
		for (int i=0; i<N; i++) {
			int s = Integer.parseInt(rd.readLine());
			if (i % 2 == 0) d[s]++;
			else u[H-s+1]++;
		}
		
		U = new int[H+1];
		D = new int[H+1];
		for (int i=H-1; i>0; i--)
			D[i] = D[i+1] + d[i];
		for (int i=2; i<=H; i++) {
			U[i] = U[i-1] + u[i];
		}
		
		min = Integer.MAX_VALUE;
		for (int i=1; i<=H; i++) {
			int c = U[i] + D[i];
			if (min > c) {
				min = c;
				cnt = 1;
			}
			else if (min == c) {
				cnt++;
			}
		}
		
		System.out.println(min + " " + cnt);
	}
}

메모리 및 시간

• 메모리: 34996 KB
• 시간: 340 ms

리뷰

• 처음에는 누적합을 쓰지 않고 $O(NH)$의 알고리즘을 사용했는데, 나중에 보니 시간초과를 받고 누적합으로 고치게 되었다.
• u와 d를 정렬한 후 이분탐색을 쓰는 방법도 있는 것 같다.