[백준] 20207 - 달력

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

20207번: 달력

 

주어지는 일정을 어떻게 저장하고 관리하는지가 관건인 문제였다.

 

먼저 주어지는 조건에 맞게 입력을 정렬한 후, day라는 1차원 배열에 시작~끝 구간만큼 1씩 증가시켜준다.

 

만약 어떤 날의 day 배열 값이 3이라면 해당 일자에는 3개의 일정이 중복되어있다는 뜻이므로, 해당 일자의 직사각형의 높이는 3이 된다.

만약 어떤 날의 day 배열 값이 0이라면 해당 일자에는 일정이 없고, 이전까지 나왔던 일정의 직사각형의 넓이를 구하면 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int n, ar[366];
pair<int, int> a[1000];

bool compare(pair<int, int>& p1, pair<int, int>& p2) {
	
	if (p1.first == p2.first) {
		return p1.second - p1.first < p2.second - p2.first;
	}

	return p1.first < p2.first;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
		for (int j = a[i].first; j <= a[i].second; j++) {
			ar[j]++;
		}
	}

	sort(a, a + n);
	
	int w = 0, h = 0, ans = 0;

	for (int i = 1; i <= 365; i++) {
		if (ar[i]) {
			h = max(h, ar[i]);
			w++;
		}
		if (!ar[i] || i == 365) {
			ans += h * w;
			h = 0;
			w = 0;
		}
	}

	cout << ans;
}