[BOJ] 3020. 개똥벌레

누적합을 사용한 문제였다.

문제를 맨처음 봤을때 단순히 브루트포스로 접근하여 모든 라인에서 모든 장애물을 카운트하는 방식을 사용하려고 했으나, 최대 장애물의 수가 200,000개, 최대 라인의 수가 500,000이 나오게 됨으로 시간초과를 피할수 없을것같다는 생각이 들었다. 그래서 생각해본게 높이당 장애물의 수를 저장하고, 그것을 이용하여 높이당 넘어야할 장애물의 누적수를 구한다음 모든 높이(라인)에서 몇개의 장애물을 넘어야하는지 계산하였다. 다만 주의할점은 장애물이 위방향, 아래방향 두가지가 나오게 됨으로 나누어서 계산을하고 인덱스를 적절히 조정하여 높이(라인)에서 몇개의 장애물을 넘는지 구하였다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_3020_개똥벌레 {
    static int N, height;
    static int[] forwardObstacle;
    static int[] reverseObstacle;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        height = Integer.parseInt(st.nextToken());
 
        //1부터 height까지의 바위의 높이당 갯수를 저장할 배열
        forwardObstacle = new int[height + 1];
        reverseObstacle = new int[height + 1];
 
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            if (i % 2 == 0) {
                forwardObstacle[num] += 1;
            } else {
                reverseObstacle[num] += 1;
            }
        }
 
        //1부터 height까지의 바위 누적합을 저장할 배열
        int[] forwardSum = new int[height + 1];
        int[] reverseSum = new int[height + 1];
 
        //가장 높은곳은 직접 지정
        forwardSum[height] = forwardObstacle[height];
        reverseSum[height] = reverseObstacle[height];
 
        //그 후 하나 높은 곳의 누적합 + 현재 높이의 갯수
        for (int i = height - 1; i >= 1; i--) {
            forwardSum[i] = forwardSum[i + 1] + forwardObstacle[i];
            reverseSum[i] = reverseSum[i + 1] + reverseObstacle[i];
        }
 
        //N개를 넘는 누적합을 저장하는 배열
        int[] obstacleToAvoid = new int[N];
 
        for (int i = 1; i <= height; i++) {
            //forward는 정방향임으로 i, reverse는 역방향이기에 height+1-i
            int sum = forwardSum[i] + reverseSum[height + 1 - i];
            obstacleToAvoid[sum] += 1;
        }
 
        for (int i = 0; i <= N; i++) {
            if (obstacleToAvoid[i] != 0) {
                System.out.println(i + " " + obstacleToAvoid[i]);
                break;
            }
        }
    }
}