[KOITP] 동굴

출처 : http://koitp.org/problem/COCI_2007_FIREFLY/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	1486	340 (23%)	284

문제

벌레 한 마리가 동굴을 지나려고 한다. 모두가 알다시피 동굴은 석순과 종유석이 굉장히 많은 공간이다. 이 벌레는 이렇게 장애물이 많은 동굴을 지나갈 것이다. 동굴의 길이는 N미터이고, 높이는 H미터이다. N은 항상 짝수이고, 장애물은 석순과 종유석이 번갈아 가면서 등장하고, 첫 장애물을 항상 석순이다.

아래 예제는 N=14, H =5의 예이다.

남자다운 이 벌레는 장애물을 굳이 피하지 않는다. 즉, 처음 정한 높이에서 일직선으로 장애물을 부수면서 지나간다. 벌레가 아래에서 4번째 구간으로 지나가면, 아래 그림과 같이 8개의 장애물을 부수게 된다.

하지만, 첫 번째나 다섯 번째 구간으로 날아간다면 벌레는 7개의 장애물만 부시면 된다.

벌레는 아픔을 느끼는 남자이기 때문에, 최소한의 장애물만 부시고 싶어한다. 여러분은 이 벌레가 최소 몇 개의 장애물만 부수고도 통과할 수 있는지 구하고, 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

두 번째 줄부터 N개의 줄에 걸쳐 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력

첫 번째 줄에 개똥벌레가 파괴해야 하는 장애물의 최소값과 그러한 구간의 수를 공백으로 구분하여 출력하시오.

힌트

예제 입력

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

예제 출력

7 2

< Comment >

 발상이 무척 어려웠고, 처음에 설명을 듣고도 잘 이해가 안 갔습니다. 왜 입력을 받고 더하고 하는지 잘 이해가 안 되었는데, 찬찬히 살펴보니 그다지 어려운 내용은 아니었지만, 개인적으로는 배열을 두개로 나누는 것이 편해서 나누어 코딩했습니다. 각각 배열의 의미는 처음에 입력할 때는 각 배열 index를 높이로 가지는 배열이지만, 이후에 작업을 하고 난 후에는 index 높이로 지나갈 경우 부딪히는 종유석/석순의 수로 보게 됩니다. 시간제한 때문에 전체탐색은 일단 배제되며, 이렇게 종유석과 석순을 각 높이로 진행할 경우로 계산합니다. 석순같은 경우에는 그대로 해석하면 되지만 종유석 같은 경우에는 위에서부터 진행되기 때문에 석순 입장에서 i 높이라면 종유석에서는 H - i + 1 인덱스로 지나갔다고 볼 수 있기 때문에, 둘을 합친 값들 중에 최소값을 구하면 결과가 도출됩니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Cave {
	
	public static int N = 0;
	public static int H = 0;
	
	public static int bot[] = null;
	public static int top[] = null;

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		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];
		
		int curr = 0;
		for (int i = 0 ; i < N ; i++) {
			
			curr = Integer.parseInt(br.readLine());
			if (i % 2 == 0) {				
				bot[curr]++;
			} else {
				top[curr]++;
			}
		}
		
		for (int i = H ; i > 0 ; i--) {
			
			bot[i - 1] += bot[i];
			top[i - 1] += top[i];
		}
		
		
		int result[] = new int[H+1];
		int min = Integer.MAX_VALUE;
		for (int i = 1 ; i <= H ; i++) {
			
			result[i] = bot[i] + top[H - i + 1];
			min = Math.min(min, result[i]);
		}
		
		int count = 0;
		for (int i = 1 ; i <= H ; i++) {
			
			if (min == result[i]) {
				count++;				
			}
		}
		
		bw.write("" + min + " " + count);
		bw.flush();
		bw.close();
	}
}