백준 16396번: 선 그리기

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

16396번: 선 그리기

각 지점 i에 대해 (i에서 시작하는 선의 개수) - (i 직전에 끝나는 선의 개수)를 배열 cnt에 각각 저장한다고 하자. 모든 선의 시작점과 끝점을 입력받으며 cnt를 완성한 뒤, 0번 지점부터 각 지점을 순차적으로 탐색하며 i번 지점까지의 cnt의 합을 sum[i]라고 할 때, sum[i]가 양수라면 시작점이 끝점보다 많다는 뜻이므로 아직 끝나지 않은 선이 존재한다. 따라서 각 지점에 대해 sum을 구한 뒤, sum이 양수인 지점의 개수를 저장해 출력하면 정답이 된다.

#include <cstdio>

#define MAX 10000

int main() {
    // N: 선의 개수, X, Y: 각 선의 시작점과 끝점, ans: 투사한 선의 총 길이
    int N, X, Y, sum = 0, ans = 0;
    // chk[i]: 지점 i에서 시작하는 선의 개수 + 지점 i 직전에서 끝나는 선의 개수
    short chk[MAX + 1] = { 0, };

    // 각 선에 대해
    for (scanf("%d", &N); N--; ) {
        // 선의 시작점과 끝점을 입력받고 이를 chk에 저장
        scanf("%d %d", &X, &Y);
        chk[X] += 1; chk[Y] -= 1;
    }

    // 선의 각 지점에 대해
    for (int i = 0; i <= MAX; i++) {
        // 해당 지점에서의 시작점과 끝점의 차를 sum에 더한 뒤
        sum += chk[i];
        // sum이 양수라면 아직 끝나지 않은 선이 존재하므로 ans에 1을 더한다
        ans += (sum > 0);
    }

    // 투사한 선의 총 길이를 출력
    printf("%d\n", ans);

    return 0;
}