[백준] 20207번

www.acmicpc.net

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

문제

💡

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

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

연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다.

연속된 모든 일정은 하나의 직사각형에 포함되어야 한다.

연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.

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

일정은 시작날짜와 종료날짜를 포함한다.

시작일이 가장 앞선 일정부터 차례대로 채워진다.

시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.

일정은 가능한 최 상단에 배치된다.

일정 하나의 세로의 길이는 1이다.

하루의 폭은 1이다.

시간 제한: 1초

메모리 제한: 512MB

입력

💡

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

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

출력

💡

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

예제 입력	예제 출력
7 2 4 4 5 5 6 5 7 7 9 11 12 12 12	28
5 1 9 8 9 4 6 3 4 2 5	36

풀이

코드를 구현하는데에는 시간이 얼마 안걸렸지만, 문제를 완전히 파악하는데 시간이 많이 걸렸다. 필요한 것은 가로 길이와 세로 길이이다.

모든 배열을 0으로 초기화 한 뒤, 배열에 블럭을 채워넣는 행위를 해당 인덱스 원소값 +1로 바꾸면 가로는 0보다 큰 원소가 연속되는 길이가 되고, 세로는 그 원소들 중 가장 큰 값이 된다.

이 방식을 사용하면 몇몇 일정배치 규칙을 고려하지 않아도 된다.

연속이 끊기는 부분을 0인지 검사하는 방식으로 구현했는데, 1일부터 365일까지 일정이 연속하는 경우 0이 검사되지 않아 마지막에 예외로 처리했다.

코드


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

int main() {
    vector<int> calendar(365, 0);
    int n, s, e;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> s >> e;
        for (int j = s - 1; j <= e - 1; ++j) {
            calendar[j] += 1;
        }
    }
    
    int width = 0;
    int hight = 0;
    int result = 0;

    for (int i = 0; i < 365; ++i) {
        if (calendar[i] != 0) {
            hight = max(hight, calendar[i]);
            width += 1;
        }
        else {
            result += width * hight;
            hight = 0;
            width = 0;
        }
    }
    
    if (hight != 0 && width != 0) result += width * hight;
    
    cout << result;
    return 0;
}

[백준] 20207번 - 달력

문제

입력

출력

풀이

코드