[Java] 백준 20207번 - 달력

• 문제
  • 링크 : https://www.acmicpc.net/problem/20207
  • 코팅지의 면접

 

• 조건
  • 코팅지 규칙
    • 연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다.
    • 연속된 모든 일정은 하나의 직사각형에 포함되어야 한다. 
    • 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.
  • 달력 규칙
    • 일정은 시작날짜와 종료날짜를 포함한다.
    • 시작일이 가장 앞선 일정부터 차례대로 채워진다.
    • 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.
    • 일정은 가능한 최 상단에 배치된다.
    • 일정 하나의 세로의 길이는 1이다. 
    • 하루의 폭은 1이다.

 

• 입력
  • 첫번째 줄 : N(일정의 개수, 1 ≤ N ≤ 1,000)
  • 두번째 줄 ~
    • S : 시작 날짜
    • E : 종료 날짜
    • 1 ≤ S ≤ E ≤ 365

 

• 출력
  • 코팅지의 면접

 

• 로직 1)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 일정 개수
        int answer = 0; // 코팅지 넓이
        int[] calendar = new int[366]; // 일정 개수
        int start, end;

        // 일정 등록하기
        for(int i=0; i<N; i++) {
            start = sc.nextInt();
            end = sc.nextInt();

            for(; start <= end; start++) {
                calendar[start]++;
            }
        }

        // 직사각형 넓이 구하기
        int height = 0;
        int width = 0;
        int cur;
        for(int i=1; i<calendar.length; i++) {
            cur = calendar[i];
            if(cur>0) {
                if(cur > height) height = cur;
                width++;
            }
            if((cur==0 && height != 0) || i == calendar.length-1) {
                answer += height * width;
                height = 0;
                width = 0;
            }
        }

        System.out.println(answer);
    }
}

 

• 결과
  • 맞았습니다.