[BOJ] 14595. 동방 프로젝트 (Large) (🥇, 누적합)

🔗

풀이

전체 방 N의 최대값은 백만이고 빅-종빈빌런이 행동을 수행하는 횟수는 최대 M이기 때문에 M번의 행동을 할 때마다 깨부수는 벽들의 정보에 대해서 일일이 확인하는 방식은 시간초과가 발생할 수 있을 것 같다.

빅-종빈빌런이 방을 부술 때는 연속해서 있는 벽들을 허문다는 규칙이 있다. 1번부터 3번까지, 2번부터 4번까지 연속해서 허물게 되기 때문에 모든 벽들에 대한 정보를 저장해둘 필요 없이 벽의 시작과 끝에 대한 정보만 저장하고 M번의 행동이 끝난 후 한 번에 처리하면 될 것 같았다.

현재 필요한 정보는 방이 아니라 벽이고, 방이 N개라면 벽은 N+1개가 된다. 방은 1번부터 시작하고 벽은 0번부터 시작한다고 했을 때 1번부터 3번까지 방 사이의 벽들을 허문다는 것은 1, 2번 벽을 허문다는 뜻이 된다.

1, 2번 벽에 대해 표시를 해줘야 하기 때문에 1번부터 시작해서 2번에서 끝나도록 하기 위해서 1번에 +1, 3번에 -1을 한다. 해당 과정을 반복하면 아래와 같은 결과가 나오게 된다.

[0, 1, 2, 1, 0, 1, 1, 1, 0, 0, 0]

0은 벽이 존재한다는 것이고, 0보다 큰 숫자들은 벽이 허물어져 없는 곳이다. 해당 과정들이 반복될 수 있기 때문에 중복되어서 숫자가 커지는 것이지 0을 제외한 각 숫자들에 큰 의미는 없다.

그림으로 표현하면 위와 같다.

방이란 개념은 결국 양 옆에 두 개의 벽이 있어야 완성되므로, 방의 개수를 세기 위해서는 벽 두 개 중 하나의 개수만 세면 된다. 오른쪽에 남아있는 벽의 개수 = 방의 개수가 되는 것이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[] walls = new int[N+1];
        int x;
        int y;
        StringTokenizer st;
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            walls[x] += 1;
            walls[y] -= 1;
        }

        for (int i = 1; i <= N; i++) {
            walls[i] += walls[i-1];
        }
        
        int room = 0;
        for (int i = 1; i <= N; i++) {
            if (walls[i] == 0) room++;
        }

        System.out.println(room);
    }
}