[백준 / BOJ] 3020 개똥벌레

https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

전형적인 누적합 문제였다.

 

개똥벌레가 석순과 종유석을 피하지 않기 때문에, 결국 해당 높이에 몇 개의 장애물이 있는지만 파악하면 된다. 따라서 높이인 H만큼의 크기를 가진 배열 sum을 만들었다. sum[0]은 가장 아래, 즉 석순이 자라는 바닥이고, sum[H-1]은 종유석이 자라는 천장이다.

 

항상 석순 - 종유석 - 석순 - 종유석 순으로 나타나기 때문에 i가 짝수인지 홀수인지를 확인했다. 이에 따라 석순은 바닥(sum[0])부터 석순의 길이까지(sum[n-1]), 종유석은 천장(sum[H-1])부터 종유석의 길이(sum[H - n])까지 채워야함을 알 수 있다. 즉 다음과 같다. 

int[] sum = new int[H];
for (int i = 0; i < N; i++) {
	int n = Integer.parseInt(br.readLine());
			
	if(i % 2 == 0) { // 석순
		sum[0]++;
		sum[n]--;
	} else { // 종유석
		sum[H - n]++;
	}
}

 

 

이제 누적합을 사용하여 sum[i] += sum[i-1]을 진행한다. 이와 동시에 min 값을 찾아주었다.

 

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int H = Integer.parseInt(st.nextToken());
		
		int[] sum = new int[H];
		for (int i = 0; i < N; i++) {
			int n = Integer.parseInt(br.readLine());
			
			if(i % 2 == 0) { // 석순
				sum[0]++;
				sum[n]--;
			} else {
				sum[H - n]++;
			}
		}
		
		
		int cnt = 1;
		int min = sum[0];
		for (int i = 1; i < H; i++) {
			sum[i] += sum[i-1];
			if(sum[i] < min) {
				min = sum[i];
				cnt = 1;
			} else if(sum[i] == min) {
				cnt++;
			}
		}
		
		System.out.println(min + " " + cnt);
	}

}