20207번 달력

문제 설명

이번 문제는 다음과 같은 달력에 일정을 표시해둘 경우 코팅지를 사용하는데, 다음과 같은 규칙으로 코팅지를 붙일 경우 필요한 코팅지의 면적을 구하는 문제입니다.

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

달력은 다음 규칙을 따릅니다.

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

일정에 따라 코팅지를 달력에 붙인 예시

사용한 코팅지의 면적

 

문제 풀이

아이디어

정렬

일정을 붙이는 것에 순서가 있다보니 일정을 원하는 순서대로 정렬을 한 뒤 다음 풀이를 이어나가는 것이 좋을 것 같다고 생각했습니다.

 

문제의 규칙에 일정의 시작 날짜가 앞선 일정부터 차례대로 채워진다고 했으므로, 일정의 시작 날짜가 앞선 것들을 배열의 앞쪽에 위치하도록 하도록 했습니다.

그리고, 문제에서 시작 날짜가 같다면 일정의 기간이 긴 것이 먼저 채워진다고 했으므로, 시작 날짜가 같은 것은 종료 날짜가 늦은 것이 배열의 앞쪽에 위치하도록 정렬해줍니다.

 

같은 코팅지를 사용할 조건

이전의 일정과 같은 코팅지를 사용할 경우는 현재 일정의 시작 날짜가 이전까지 사용한 코팅지의 {종료날짜+1} 이하여야 됩니다.

(문제의 규칙에서 연속된 일정을 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다고 했으므로)

 

코팅지의 세로 길이

현재의 일정에 이미 코팅지가 있다면 이 코팅지는 그 아래에 붙여야 합니다.

앞선 일정 때문에 이미 코팅지가 붙어있음을 알기 위해서, 현재 관여하고 있는 코팅지의 각 높이에 대해 시작과 종료 날짜를 저장해둡니다.

현재 층의 종료 날짜와 현재 일정의 시작 날짜를 비교해 해당 달력의 층에 붙일 수 있는지 알 수 있습니다.

 

예시)

위의 사진에서 입력받은 일정을 위의 정렬 순서대로 정렬하고, 달력의 1층은 [2,7]([해당 층의 시작 날짜, 해당 층의 종료 날짜]), 2층은 [4,5], 3층은 [5,6]으로 나타나 있고 (시작 날짜가 7 종료날짜가 9)인 일정에 대한 코팅지를 붙이려고 할 때를 생각해보겠습니다.

 

1층에서는 시작 날짜와 종료날짜가 2,7 이므로 7일에 이미 코팅지가 붙어있으므로 넘어갑니다.

2층은 시작날짜와 종료날짜가 4,5 이므로 해당 일정에 코팅지가 붙어있지 않습니다. 그러므로 해당 일정은 2층에 붙이게 됩니다.

 

풀이

정렬

python의 cmp_to_key 를 통해 custom sort 함수를 만들어줍니다.

입력받은 시작 날짜와 종료 날짜를 시작 날짜가 빠른 순으로, 시작 날짜가 같다면 종료 날짜가 늦은 순으로 정렬해줍니다.

def compare(prev,curr):
    if prev[0]==curr[0]:
        return curr[1]-prev[1]
    else:
        return prev[0]-curr[0]

 

정렬된 배열을 s_e_list에 저장합니다.

 

코팅지 붙이기

s_e_list를 for문을 통해 반복하면서 다음을 행합니다.

• 코팅지의 시작 날짜와 종료 날짜를 저장합니다. (각각 s, e에 저장)
• 현재 일정의 시작 날자가 {코팅지의 종료 날짜 + 1}보다 크다면 새로운 코팅지를 시작하고, 현재 일정의 시작날짜와 종료날짜를 s와 e에 저장합니다.
• 현재 일정이 코팅지의 1층에 붙일 공간이 있다면, 해당 코팅지 1층에 대한 종료 날짜를 현재 일정의 종료날짜로 변경 해줍니다.
• 현재 일정이 코팅지의 1층에 붙일 공간이 없다면, 해당 코팅지의 2층에 붙일 공간이 있는지 확인합니다. 2층에 붙일 공간이 없다면 3층에 .... (붙일 수 있을 때까지 반복)
• 모든 일정에 대해 반복합니다.

 

 

해결

이번 문제는 일정과 관련된 참신한 문제였던 것 같습니다.

 

문제 링크 : https://www.acmicpc.net/problem/20207

20207번: 달력

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/20207.py