[문제풀이] 백준 20207 - 달력

📢 문제

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

📢 알고리즘

구현, 그리디 알고리즘

📢 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int yearCnt[366] = {0}; // 각 날짜의 일정 개수

bool compare(pair<int, int> p1, pair<int, int> p2)
{
  if (p1.first != p2.first)
  {
    return p1.first < p2.first; // first는 오름차순
  }
  else
  {
    // second는 내림차순
    return p1.second > p2.second;
  }
}

int main()
{
  int N;
  cin >> N;
  vector<pair<int, int>> v;

  v.resize(N);
  for (int i = 0; i < N; i++)
  {
    int start, end;
    cin >> start >> end;
    v[i] = make_pair(start, end);
  }
  sort(v.begin(), v.end(), compare);

  // 일정 배치
  int width = 0;
  int height = 0;
  int sum = 0;

  for (const auto e : v)
  {
    for (int i = e.first; i <= e.second; i++)
    {
      yearCnt[i]++;
    }
  }

  // 한 날에 일정이 0개면 사각형 끊김
  for (int i = 1; i <= 365; i++)
  {
    if (yearCnt[i] > 0)
    {
      width++;
      height = max(height, yearCnt[i]);
    }
    else
    {
      // 사각형 계산
      sum += width * height;
      width = 0;
      height = 0;
    }
  }
  sum += width * height;
  width = 0;
  height = 0;

  cout << sum;
}

• yearCnt(각 날짜에 일정이 총 몇개인지)가 핵심!!

  • 👉 yearCnt가 0이면(특정 날짜에 일정이 하나도 없으면) 코팅지 사각형 자름
    👉 자르기 직전에 코팅지 사각형의 가로길이 구할 수 있음
    👉 yearCnt의 최대값이 코팅지 사각형의 높이

• 처음에는 일정 상태 그대로 배열을 채운 후 직접 코팅지 사각형 넓이 구하고.. 그랬는데...
  이렇게 딱 필요한 값만 구하는 방법이 있다니...

참고
https://codecollector.tistory.com/1159#%F0%9F%93%94-%EC%A0%95%EB%8B%B5%EC%B6%9C%EB%A0%A5