백준 20207 - 달력 (C++)

 

일정을 규칙에 따라 차례대로 달력에 기록한다.

일정이 겹치면, 해당 일정은 아랫줄에 추가로 기록한다.

 

모든 일정을 기록한 뒤, 직사각형의 코팅지를 일정 위에 붙인다고 했을 때, 최소로 필요한 코팅지의 면적을 구하면 된다.

 

문제 풀이

 

본인은 365일을 기록하는 벡터를 만든 뒤, 해당 벡터에 일정을 모두 기록하여 문제를 해결하였다.

7
2 4
4 5
5 6
5 7
7 9
11 12
12 12

 

입력이 위와 같이 주어졌다고 해보자.

이렇게, 모든 날의 일정을 기록할 벡터를 선언하였다.

이후, 일정을 차례대로 입력할 것이다.

 

문제 예시를 보면, 겹치는 일정이 하나가 생길 때마다 높이가 1씩 증가한다.

그러므로, 한 날짜에 일정이 부여될 때마다 ++을 해줄 것이다.

 

(만약, 5일에 5개의 일정이 있다면, 5번 인덱스의 값은 5가 된다.)

 

이제 차례대로 입력을 처리해보자.

첫 번째 입력은 2 4 이다.

이렇게 2~4에 1을 더해주었다.

다음 입력은 4~5이다.

이번엔, 4와 5에 1을 더해서 위 표와 같은 값으로 갱신되었다.

다음 입력은 5~6이다.

위 표와 같이 갱신되었다.

다음 입력은 5~7이다.

이렇게 갱신되었다.

동일한 방식으로 나머지 모든 입력을 처리해주면 아래와 같아질 것이다.

 

이렇게, 일정을 모두 기록하였다면 코팅지의 최소 크기를 구하면 된다.

먼저, 일정이 없는 날에는 코팅지를 붙일 필요가 없다.

그러므로 일정이 있는 날에 대해서만 코팅지의 크기를 계산해줄 것이다.

 

 

먼저, 이 두개의 섹션에 대해서만 코팅지를 붙이면 된다.

각 섹션의 길이가 코팅지의 가로 길이일 것이다.

 

코팅지의 세로 길이는 그 안에 있는 모든 일정을 담아야 하기 때문에, 섹션에 포함된 값들 중 가장 큰 값이 코팅지의 세로 길이가 될 것이다.

 

그러므로, 왼쪽 섹션의 코팅지의 세로 길이는 3이 될 것이며 오른쪽 섹션의 코팅지의 세로 길이는 2가 될 것이다.

 

왼쪽 섹션의 코팅지의 넓이 : 가로 길이 * 세로 길이 = 8 * 3 = 24

오른쪽 섹션의 코팅지의 넓이 : 가로 길이 * 세로 길이 = 2 * 2 = 4

 

정답 = 24 + 4 = 28 이 된다.

 

풀이 코드

int InputSize = 0;
std::cin >> InputSize;

std::vector<std::pair<int, int>> Schedules(InputSize);

for (int i = 0; i < InputSize; i++)
{
    std::cin >> Schedules[i].first >> Schedules[i].second;
}

 

먼저, 입력되는 일정 정보를 vector에 저장해주었다.

 

std::vector<int> Days(367);

for (int i = 0; i < InputSize; i++)
{
    for (int j = Schedules[i].first; j <= Schedules[i].second; j++)
    {
        Days[j]++;
    }
}

 

이후, 일정을 기록할 Days 배열을 선언한 뒤, 모든 일정을 기록해주었다.

일정이 하나 겹칠 때마다 1씩 값을 증가시켜주었다.

 

여기서 Days의 길이가 365가 아니라, 367인데 이유는 아래에서 확인해보자.

int Start = 0;
int MaxY = 0;
int Sum = 0;

for (int i = 1; i <= 366; i++)
{
    if (Days[i - 1] != 0 && Days[i] == 0)
    {
        Sum += MaxY * (i - Start);
        MaxY = -1;
    }
    else if (Days[i - 1] == 0 && Days[i] != 0)
    {
        Start = i;
    }

    if (Days[i] != 0)
    {
        MaxY = std::max(MaxY, Days[i]);
    }
}

 

먼저, 시작 인덱스와 섹션의 최대 값을 저장할 Start와 MaxY를 선언해주었고, 정답을 저장할 Sum도 선언해주었다.

 

여기서, 각 섹션의 시작을 값이 0인 인덱스에서 0이 아닌 인덱스로 변화하는 시점으로 잡아주었다. 또한, 섹션의 끝은 값이 0이 아닌 인덱스에서 값이 0으로 변하는 시점으로 잡아주었다.

 

이 때, 시작부터 끝까지 모든 섹션을 동일하게 처리하기 위해, 배열을 367칸으로 선언하여 0번 인덱스와 366번 인덱스를 활용하였다.

 

만약 0~364로 선언된 배열이었을 때, 마지막 일정이 365일에 끝난다면 해당 일정이 속한 섹션을 반복문 내에서 처리할 수 없기 때문에 추가적으로 코드를 작성해야 한다.

 

그렇게 각 섹션의 길이와 최대값을 구한 뒤, 섹션을 탈출할 때 두 값을 곱해 코팅지의 넓이를 구하고 Sum에 더해주었다.

 

std::cout << Sum;

return 0;

 

마지막으로 답을 출력해주면 된다.

 

코드 전문

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

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int InputSize = 0;
    std::cin >> InputSize;

    std::vector<std::pair<int, int>> Schedules(InputSize);

    for (int i = 0; i < InputSize; i++)
    {
        std::cin >> Schedules[i].first >> Schedules[i].second;
    }

    std::vector<int> Days(367);

    for (int i = 0; i < InputSize; i++)
    {
        for (int j = Schedules[i].first; j <= Schedules[i].second; j++)
        {
            Days[j]++;
        }
    }

    int Start = 0;
    int MaxY = 0;
    int Sum = 0;

    for (int i = 1; i <= 366; i++)
    {
        if (Days[i - 1] != 0 && Days[i] == 0)
        {
            Sum += MaxY * (i - Start);
            MaxY = -1;
        }
        else if (Days[i - 1] == 0 && Days[i] != 0)
        {
            Start = i;
        }

        if (Days[i] != 0)
        {
            MaxY = std::max(MaxY, Days[i]);
        }
    }

    std::cout << Sum;

    return 0;
}