[백준 20207번/c++] 달력

문제

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

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

20207번: 달력

 

---

조건

일정이 있는 곳에 코팅지를 달력에 붙인다.

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

달력은 다음과 같은 규칙을 가진다.

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

 

---

입출력

입력

• 일정의 개수 N (1<=N<=1000)
• 일정의 개수만큼 시작 날짜 S와 종료 날짜 E (1<=S<=E<=365)

출력

• 코팅지의 면적을 출력

 

---

문제에서 주어진 예시

문제에서 주어진 예를 통해 살펴보자.

 

 

 

---

코드 구현

1. 시작일 기준 오름차순으로 정렬
2. 시작일이 같은 경우, 종료일 기준 내림차순으로 정렬
3. 정렬된 배열을 하나씩 탐색하며 색칠
4. 이때 색칠하면서 코팅할 직사각형을 찾아 넓이 계산

 

😯 코팅할 직사각형은 어떻게 찾아야할까?

현재 색칠하는 스케줄의 시작일자 > 이전까지 색칠한 스케줄의 종료 일자의 최댓값 + 1

 

-> 직사각형이 하나 만들어진 것

 

위의 예시로 살펴보면

이 상황에서 11~12를 색칠하게 되는데

현재 색칠하는 스케줄의 시작일자(11)이 이전까지 색칠한 스케줄의 종료 일자의 최댓값 + 1(9+1=10)보다 크므로 직사각형 하나가 만들어진 것이다. 

 

---

구조체를 원소로 가지는 벡터 배열 정렬하기

스케줄의 시작 날짜와 종료 날짜를 저장하는 구조체 배열이 다음과 같이 있을 때, 

struct schedule{
    int s, e;

    schedule(int s, int e){
        this->s=s;
        this->e=e;
    }
};

 

시작일 기준 오름차순으로 정렬하기 위해서는 다음과 같이 작성한다.

int cmp(schedule s1, schedule s2){
	return s1.s<s2.s;
}

 

시작일이 같은 경우, 종료일 기준 내림차순 정렬을 하기 위해 조건문을 추가하여 다음과 같이 작성한다.

int cmp(schedule s1, schedule s2){
    if(s1.s==s2.s){
        return s1.e>s2.e;
    } else{
        return s1.s<s2.s;
    }
}

 

정렬 시 해당 함수를 함께 주어 정렬이 이루어지도록 한다.

sort(schedules.begin(), schedules.end(), cmp);

 

---

성공 코드(내 코드)

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

struct schedule{
    int s, e;

    schedule(int s, int e){
        this->s=s;
        this->e=e;
    }
};

int cmp(schedule s1, schedule s2){
    if(s1.s==s2.s){
        return s1.e>s2.e;
    } else{
        return s1.s<s2.s;
    }
}

vector<schedule> schedules;
vector<vector<int> > calendar(1001, vector<int>(366, 0));
int N, maxScheduleCnt=0, startCoting, endCoting=0;

int writeSchedules(){
    int answer=0;
    startCoting=schedules[0].s;
    for(int i=0; i<N; i++){
        int s=schedules[i].s, e=schedules[i].e;
        int idx=1;
        if(endCoting+1<schedules[i].s){
            answer+=(endCoting-startCoting+1)*maxScheduleCnt;
            startCoting=schedules[i].s;
            maxScheduleCnt=0;
        }
        if(endCoting<e){
            endCoting=e;
        }
        while(s<=e){
            if(calendar[idx][s]==1){
                idx++;
            } else{
                calendar[idx][s]=1;
                if(idx>maxScheduleCnt){
                    maxScheduleCnt=idx;
                }
                s++;
            }
        }
    }
    answer+=(endCoting-startCoting+1)*maxScheduleCnt;

    return answer;
}

int main() {
	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    int S, E;

    cin >> N;
    for(int i=0; i<N; i++){
        cin >> S >> E;
        schedules.push_back(schedule(S, E));
    }
    sort(schedules.begin(), schedules.end(), cmp);

    cout << writeSchedules();
	
	return 0;
}

---

후기

정렬과 직사각형 크기를 구하는게 문제의 핵심이었던 것 같다. 이번 문제를 풀면서 구조체를 원소로 가지는 벡터가 있을 때 정렬하는 함수를 작성하고 적용시키는 것에 대해 정확히 알 수 있었다.👍