[C++] BOJ 20207번 : 달력

 

 

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

 

문제 3줄 요약

1. 달력에 1년치 일정을 표시하려고 한다.

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

3. 연속된 일정을 하나의 직사각형에 포함하여 달력에 코팅지를 붙일 때, 코팅지의 넓이는?

 

---

 

구현 문제라서 그런가

문제부터 길고 뭔가 조건이 좀 많아서 복잡해보인다...

 

예시를 보면서 이해해보자.

 

 

위와 같이 2일 ~ 12일까지 일정은

아래의 보라색 코팅지를 붙일 수 있다.

 

2일 ~ 9일까지는 연속된 일정이기에

하나의 직사각형으로 묶고 있고

 

11일 ~ 12일은

따로 직사각형 모형으로 코팅지를 붙였기에 총 면적이 28 (= 24+4) 이다.

 

일단 일정이 주어졌을 때,

위와 같이 달력과 같은 형태로 구현해보도록 하겠다.

 

---

 

 

1. 입력 값 할당 및 배열 초기화

 

    int n;
    cin >> n;

    int max_length = 0;
    for(int i=0; i<n; i++)
    {
        int st, ed;
        cin >> st >> ed;

        max_length = max(max_length, ed);
        plan[i] = make_pair(st, ed);
    }
    
    sort(plan, plan+n, [](pair<int, int> L, pair<int, int> R){
        return L.first != R.first ? L.first < R.first : L.second > R.second;
    });

 

일정의 개수인 n만큼 (최대 1000)

일정 시작일과 종료일을 일정 배열에 담아둔다.

 

담아둔 일정들을

시작 일정이 오름차순으로,

종료 일정은 내림차순으로 정렬해주었다.

 

종료 일정을 내림차순한 이유는

 

시작일이 같다면 일정의 기간이 긴 것이 먼저 채워져야 하기 때문이다!

 

모든 일정 종료일은

후에 사용하기 위해 max_length에 담아주었다.

 

---

 

 

2. 달력 채우기

 

이제는 달력을 채워보도록 하자.

 

    int max_depth = 0;
    for(int i=0; i<n; i++)
    {
        int st=plan[i].first, ed=plan[i].second;
        int chk = 0;

        for(int depth=1; depth<1001; depth++)
        {
            if(!calendar[depth][st])
            {
                chk = depth;
                break;
            }
        }

        for(int day=st; day<=ed; day++)
            calendar[chk][day]=1;
    }

 

정렬된 일정의

시작일과 종료일을 받아와

달력의 해당 일자에 빈 곳(Depth)을 찾아 채워넣는다.

 

일정이 최대 1000개인데

1000개가 겹칠수도 있다고 가정하여

달력을 [1000개][365일] 크기로 할당해주었다.

 

시작일의 Depth가 정해지면

그 후 종료일까지는 Depth 번째 일정을 채워 넣는다.

 

채운 후

출력하면 아래와 같이 표현할 수 있겠다.

 

	2일	3일	4일	5일	6일	7일	8일	9일	10일	11일	12일
Depth	1	1	1	1	1	1				1	1
			1	1		1	1	1			1
				1	1

 

 

이제는 채워진 달력을 통해

코팅지의 면적을 구해보도록 하자!

 

---

 

3. 면적 구하기

 

사실 이번 문제에서

면적 구하기 부분을 구현할 때,

문제를 잘못 이해하여 많은 시간을 허비하였다...

 

허비했던 포인트는

'연속되는 구간'

이었다.

 

위의 예시에서

9일 ~ 12일 구간 중

 

9일	10일	11일	12일
		1	1
1			1

 

9일과 11일 ~ 12일은 일정이 겹치지 않는다.

 

만약

값이 아래와 같이 설정 되어있다면,

 

9일	10일	11일	12일
	1	1	1
1			1

 

9일 ~ 12일은 연속된 일정일까???

 

연속이 맞다..!

 

 

연속된 일자에 일정이 1개 이상이 있기만 하다면,

연속이기 때문이다.

 

따라서 끊기는 일자가 있으면 연속이 끊기는 것이다.

 

필자는 위와 같은 예시는 연속이 아니라 생각하였기에,

BFS를 통한 면적을 구했지만.. 틀렸다 ㅠ

 

 

따라서

이 부분 유의해서 풀면 되겠다!

 

    int area = 0, min_y = 0, max_x = 0, max_y = 0;

    for(int i=1; i<=max_length+1; i++)
    {
        if(!min_y && calendar[1][i]) min_y = i;

        int chk = 1;
        for(int j=1; j<1001; j++)
        {
            if(calendar[j][i])
            {
                chk = 0;
                max_x = max(max_x, j);
            }
        }

        if(chk)
        {
            area += (max_y-min_y+1)*max_x;
            min_y = 0, max_x = 0, max_y = 0;
        }
        else max_y = max(max_y, i);
    }
    
    cout << area;

 

만들었던 달력의 값들을 통해

끊기는 날(= 일정이 없는 날)이 있기 전까지

면적의 왼쪽 면을 차지할 연속 일정 시작일부터

면적의 오른쪽 면을 차지할 연속 일정 종료일,

일정의 최대 Depth까지 탐색한다.

 

연속이 끊기는 일이 왔다면,

(연속 일정 종료 일 - 연속 일정 시작일 + 1) * 최대 Depth를 하여

코팅지의 면적을 구해주면 되겠다.

 

지금까지의 기능을 합쳐보면 아래와 같이 작성할 수 있다!

 

#include <iostream>
#include <algorithm>

using namespace std;

pair<int, int> plan[1001];
int calendar[1001][367];

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음
    
    int n;
    cin >> n;

    int max_length = 0;
    for(int i=0; i<n; i++)
    {
        int st, ed;
        cin >> st >> ed;

        max_length = max(max_length, ed);
        plan[i] = make_pair(st, ed);
    }

    sort(plan, plan+n, [](pair<int, int> L, pair<int, int> R){
        return L.first != R.first ? L.first < R.first : L.second > R.second;
    });

    int max_depth = 0;
    for(int i=0; i<n; i++)
    {
        int st=plan[i].first, ed=plan[i].second;
        int chk = 0;

        for(int depth=1; depth<1001; depth++)
        {
            if(!calendar[depth][st])
            {
                chk = depth;
                break;
            }
        }

        for(int day=st; day<=ed; day++)
            calendar[chk][day]=1;
    }

    int area = 0, min_y = 0, max_x = 0, max_y = 0;

    for(int i=1; i<=max_length+1; i++)
    {
        if(!min_y && calendar[1][i]) min_y = i;

        int chk = 1;
        for(int j=1; j<1001; j++)
        {
            if(calendar[j][i])
            {
                chk = 0;
                max_x = max(max_x, j);
            }
        }

        if(chk)
        {
            area += (max_y-min_y+1)*max_x;
            min_y = 0, max_x = 0, max_y = 0;
        }
        else max_y = max(max_y, i);
    }
    
    cout << area;
    return 0;
}

 

---

 

구현 문제는 항상 복잡하고..

조건을 잘 읽어야 한다. ㅠㅠ

 

끝!