[백준 20207번] 파이썬 - 달력

백준 20207 - 달력

시간 제한 1초, 메모리 제한 512MB

# 조건

• 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다.
• 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다.
• 여름이 거의 끝나가자 장마가 시작되었고, 습기로 인해 달력에 표시한 일정이 지워지려고 한다.
• 지워지는 것을 막고자 수현이는 일정이 있는 곳에만 코팅지를 달력에 붙이려고 한다.
• 하지만 너무 귀찮았던 나머지, 다음과 같은 규칙을 따르기로 한다.
  • 연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다.
  • 연속된 모든 일정은 하나의 직사각형에 포함되어야 한다.
  • 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.
• 달력은 다음과 같은 규칙을 따른다.
  • 일정은 시작날짜와 종료날짜를 포함한다.
  • 시작일이 가장 앞선 일정부터 차례대로 채워진다.
  • 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.
  • 일정은 가능한 최 상단에 배치된다.
  • 일정 하나의 세로의 길이는 1이다.
  • 하루의 폭은 1이다.

• 위의 그림에서와 같이 일정이 주어졌다고 하자.
• 여기서 코팅지의 면적은 아래의 파란색 영역과 같다.

• 이때 코팅지의 크기의 합은 3 x 8 + 2 x 2 = 28이다.
• 일정의 개수와 각 일정의 시작날짜, 종료날짜가 주어질 때 수현이가 자르는 코팅지의 면적을 구해보자.

입력

• 첫째 줄에 일정의 개수 N이 주어진다. (1 <= N <= 1000)
• 둘째 줄부터 일정의 개수만큼 시작 날짜 S와 종료 날짜 E가 주어진다. (1<=S<=E<=365)

출력

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

# 접근 방법

• 367 크기의 schedule 리스트를 만들어준 후 일정을 받으며 아래 로직을 수행한다.
  • 주어진 plan의 시작날짜~종료날짜까지 schedule 리스트의 해당 날짜를 +1씩 해준다.
• schedule 리스트를 순회하며 스케줄이 시작하는 구간부터 0이 나오기 전까지 cnt를 더해주며 이 때 가장 큰 값을 저장해준다.
• 직사각형의 최소 크기는 연속된 일정의 크기 * 하루에 가장 많은 스케쥴 크기가 되므로 result에 더해준다.
• 크기를 367로 해준 이유는 365일 + 0번 인덱스 + 마지막 인덱스이다.
  • schedule 리스트를 순회하며 0이 아닌 구간을 카운트하기 때문에 마지막날 일정이 있다면 result에 더해지지 않으므로 마지막에 0을 추가해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
plan = []  
schedule = [0] * 367  
for _ in range(N):  
    a, b = map(int, input().split())  
    for i in range(a, b+1):  
        schedule[i] += 1  

cnt = 0  
result = 0  
max_plan = 0  
for idx, val in enumerate(schedule):  
    # 일정이 존재하면 카운트  
    if val:  
       cnt += 1  
       if val > max_plan:  
           max_plan = val  

    else:  
        result += cnt * max_plan  
        cnt = 0  
        max_plan = 0  

print(result)