(C++) - 백준(BOJ) 20207번 : 달력

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

20207번: 달력

정렬 후 구현하는 문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

 pair형 vector변수 plan을 선언합니다. 그 후 n만큼 차례대로 입력받습니다.

 이 후 조건대로 시작날이 가장 앞서고 만약 같다면 일정이 제일 긴 pair들 순으로 정렬해줍니다.

 

📔 풀이과정

직사각형을 만드는 조건은 연속된 일정이 width 즉, 너비가 되고 겹치는 날의 개수가 height 즉, 높이가 되며 다음 일정이 비어있다면 width * height를 ans에 더해준 뒤 width, height를 각각 0으로 초기화합니다.

 

📔 정답출력

ans를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define ONE_YEAR 365
using namespace std;
using pii = pair<int,int>;
int yearCnt[ONE_YEAR + 1], n, height, width, ans;
vector <pii> plan;

bool cmp(pii &a, pii &b){
    if(a.first == b.first){
        return a.second - a.first > b.second - b.first;
    }
    return a.first < b.first;
}

int main(){
    cin >> n;
    for(int i = 0,s,e; i < n; i++){
        cin >> s >> e;
        plan.push_back({s,e});
    }
    sort(plan.begin(),plan.end());

    for(auto p : plan)
        for(int j = p.first; j <= p.second; j++)
            yearCnt[j]++;

    for(int i = 1; i <= ONE_YEAR; i++){
        if(yearCnt[i]){
            height = max(height,yearCnt[i]);
            width++;
        }
        if(!yearCnt[i] || i == ONE_YEAR){
            ans += height * width;
            height = 0;
            width = 0;
        }
    }
    cout << ans;
}