[백준] 20207. 달력

문제 링크

[백준] 20207. 달력

풀이 과정

코팅지의 넓이는 이어져있는 일정들을 모두 포함하는 범위로, 높이는 해당 넓이에 가장 많이 겹치는 일정의 수로 결정됩니다.

따라서, 위와 같이 각 일정들의 시작과 끝 범위의 요소 값들을 1씩 증가시킨다면, 코팅지를 구분할 수 있게 됩니다.

코팅지의 넓이는 0을 기준으로 구할 수 있으며, 일정이 겹치게 되면 값이 누적되어 커지게 되므로 배열 요소 중 가장 큰 값이 코팅지의 높이가 됩니다.

만약, 일정의 마감일자가 365일이면, 끝이 0인지를 확인해야 하므로 주의해주어야 합니다. 저는 1차원 배열의 크기를 367로 설정하고 366까지 확인하는 방법으로 해결했습니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] height = new int[367];

        for (int i = 0; i < N; i++) {
            int S = sc.nextInt();
            int E = sc.nextInt();
            for (int j = S; j <= E; j++) height[j]++;
        }

        int answer = 0, h = 0, w = 0;

        for (int i = 1; i <= 366; i++) {
            if (height[i] == 0) {
                answer += w * h;
                w = h = 0;
                continue;
            }

            h = Math.max(h, height[i]);
            w++;
        }

        System.out.println(answer);
    }
}