백준 3020번: 개똥벌레

문제 설명

• https://www.acmicpc.net/problem/3020
• n개의 숫자가 입력될 때 숫자는 차례대로 아래에서 생겨나는 장애물, 위에서 생겨나는 장애물, ... 의 형태를 가집니다.
  행이동을 할 때 가장 적은 장애물을 지나는 경우의 수와 그때의 장애물 개수를 구하는 문제입니다.

접근법

• 첫 번째 예제입력으로 문제를 이해해 보겠습니다. 장애물이 있는 곳을 1로 표시해 보겠습니다. 이해를 돕기 위해 같은 장애물을 색으로 구분해 봤습니다.
  
  • 2,4,6행으로 지나갔을 때 2개의 장애물을 만나므로 정답은 2 3이 되는걸 쉽게 확인할 수 있습니다.

하지만 이 문제는 N과 M이 매우 커 단순히 1의 위치를 모두 표시하고 또 모든 행에 대해 장애물 개수를 확인한다면 시간초과가 발생하게 됩니다.

• 누적합을 이용해야 합니다.
  누적합은 특정 구간에 일정한 값을 더하는 작업을 효율적으로 수행할 수 있습니다.
  '[2,2,2,2,2]배열에서 1~3번째 값에 5를 더하라'는 문제를 누적합으로 해결해 보겠습니다. 이때 더하는 배열 [0,5,5,5,0]를 생성해 주어진 배열에 더하면 문제를 만족하게 됩니다. [0,5,5,5,0]을 구하는 건 배열 [0,5,0,0,-5]를 누적합 하는 것과 동일합니다([0,5,0,0,-5]의 누적합 -> [0,5,5,5,0]).
  이 방법은 a에서 b까지 x를 더하라는 연산을 cumSum[a] = x, cumSum[b+1] = -x로 둔 뒤 cumSum배열을 누적합 하는 방법으로 구한다고 이해하면 됩니다.
  그리고 더하는 연산이 많을 때 더욱 효율적입니다. 1~3번째 값에 5를 더하고, 0~2번째 값에 4를 더하라'는 연산을 수행할 때 위와 같은 방식을 사용하면 [4,5,0,-4,-5]이 됩니다. 실제로 해당 배열을 누적합 하면 [4,9,9,5,0]으로 1~3번째 값에 5를 더하고, 0~2번째 값에 4를 더하는 것과 결과가 동일합니다.

해당 풀이 방법은 2022 카카오 신입 공채 1차 온라인 코딩테스트 해설 - 파괴되지 않는 건물 설명에 나오는 내용입니다. 링크에서 제가 적은 설명보다 훨씬 더 깔끔하고 명확하게 설명해 주시고 있기 때문에 링크의 해설을 꼭 읽어보시길 추천드립니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		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[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		int[] cumSumArr = new int[H+2];
		fillCumSumArr(cumSumArr, arr, N, H);
		makeAnswerAndReturnIt(cumSumArr);
	}
	
	public static void fillCumSumArr(int[] cumSumArr, int[] arr, int N, int H) {
		for (int i = 0; i < N; i++) {
			int num = arr[i];
			if(i%2 == 0) {
				cumSumArr[1] += 1;
				cumSumArr[num+1] -= 1;
			}else {
				cumSumArr[H+1] -= 1;
				cumSumArr[H-num+1] += 1;
			}
		}		
		for (int i = 2; i < cumSumArr.length-1; i++) {
			cumSumArr[i] += cumSumArr[i-1];
		}		
	}
	
	public static void makeAnswerAndReturnIt(int[] cumSumArr) {
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a,b)->a-b);
		for (int i = 1; i < cumSumArr.length-1; i++) {
			pq.add(cumSumArr[i]);
		}		
		int minVal = pq.peek();
		int minValCnt = 0;
		while(!pq.isEmpty()) {
			if(minVal != pq.poll()) break;
			minValCnt++;	
		}
		
		System.out.println(minVal +" "+minValCnt);		
	}
}