달력 (백준 20207)

수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 

여름이 거의 끝나가자 장마가 시작되었고, 습기로 인해 달력에 표시한 일정이 지워지려고 한다. 지워지는 것을 막고자 수현이는 일정이 있는 곳에만 코팅지를 달력에 붙이려고 한다. 하지만 너무 귀찮았던 나머지, 다음과 같은 규칙을 따르기로 한다.

• 연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다.
• 연속된 모든 일정은 하나의 직사각형에 포함되어야 한다. 
• 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.

달력은 다음과 같은 규칙을 따른다.

• 일정은 시작날짜와 종료날짜를 포함한다.
• 시작일이 가장 앞선 일정부터 차례대로 채워진다.
• 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.
• 일정은 가능한 최 상단에 배치된다.
• 일정 하나의 세로의 길이는 1이다. 
• 하루의 폭은 1이다. 

 

위의 그림에서와 같이 일정이 주어졌다고 하자. 여기서 코팅지의 면적은 아래의 파란색 영역과 같다.

 

이때 코팅지의 크기의 합은 3 x 8 + 2 x 2 = 28이다. 

일정의 개수와 각 일정의 시작날짜, 종료날짜가 주어질 때 수현이가 자르는 코팅지의 면적을 구해보자.

입력

첫째 줄에 일정의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

둘째 줄부터 일정의 개수만큼 시작 날짜 S와 종료 날짜 E가 주어진다. (1 ≤ S ≤ E ≤ 365)

출력

코팅지의 면적을 출력한다.

예제 입력 1

7
2 4
4 5
5 6
5 7
7 9
11 12
12 12

예제 출력 1

28

예제 입력 2

5
1 9
8 9
4 6
3 4
2 5

예제 출력 2

36

---

🚀문제 해석

문제를 이해하는 것은 어렵지 않았으나 까다로운 부분은 코팅지의 넓이를 구하는 부분이었다.

먼저 그림을 그려보면서 문제를 이해하려고 했다.

 

왼쪽 그림은 입력값대로 구간을 체크해서 사각형의 넓이를 구한 것이다.

저기서 가로의 길이와 세로의 길이를 어떻게 구할 것인가가 이 문제를 해결하는 열쇠였다.

오른쪽 그림은 총 체크된 영역의 갯수를 카운팅해서 표현한 것이다. 

 

두 그림을 통해 알 수 있는 것은 가로의 길이는 체크된 영역이 존재하면 계속 누적하면서 구하면 되고, 세로의 길이는 영역마다 체크된 총 갯수 중에 최댓값을 구하면 된다는 것을 알 수 있다.

 

정리하자면 카운팅 배열을 만들어서 구간마다 일정이 존재하면 카운팅을 해주면 된다.

그리고 카운팅 배열을 활용해서 가로와 세로의 길이를 구하면 된다.

 

🛠코드 분석하기

주의할 부분은 맨 마지막이다.

예를 들어 마지막 365일까지 일정이 있는 경우에는 ch 배열을 모두 순회하여도 tmp에 값이 남아있을 수 있다.

이런 경우에는 마지막에 tmp에 값이 있는지 체크한 후, 값이 있다면 넓이를 구해 최종적으로 더해줘야한다.

let [n, ...arr] = require('fs').readFileSync(0).toString().trim().split('\n');
n = Number(n);
arr = arr.map(elem => elem.split(' ').map(Number));

function solution(n, arr) {
   const ch = Array.from({ length: 366 }).fill(0);
   // 시작 일정이 같은 경우에는 일정이 긴 것부터 체크하라는 문제 요구사항에 맞게 정렬한다.
   arr.sort(([a1, b1], [a2, b2]) => {
      if (a1 === a2) return b2 - b1;
      return a1 - a2;
   });
   // 구간 카운팅
   arr.forEach(([s, e]) => {
      for (let i = s; i <= e; i++) {
         ch[i] += 1;
      }
   });

   let tmp = [];
   let result = 0;

   ch.forEach(val => {
   // 넓이를 구하고 tmp를 초기화한다.
      if (tmp.length && val === 0) {
         result += tmp.length * Math.max(...tmp);
         tmp = [];
      } else if (val != 0) {
         tmp.push(val);
      }
   });
   // 마지막으로 tmp에 값이 남아있는지까지 체크해야한다.
   if (tmp.length) result += tmp.length * Math.max(...tmp);
   return result;
}

console.log(solution(n, arr));

 

크게 어려운 문제는 아니였지만 넓이를 구하는 과정에서 까다로움을 느꼈다. 열심히 복습하자.