[BOJ/백준] 20207 달력 파이썬

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

20207번: 달력

나는 누적합을 활용하였다.

 

달력의 시작일자에 +1 종료일자+1 에 -1을 해주었다.

해당 일자의 누적합이 사각형의 높이가 될 것이다.

그리고 1~366까지 누적합을 확인하면서 가로,세로 크기의 최대값을 갱신했다.

 

누적합 간단히 설명하면 아래와 같다.

입력이

7

2 4

4 5

5 6

5 7

7 9

11 12

12 12

라고 해보자.

시작일에 +1 종료일+1에 -1을 해준다 했다.

그럼 배열의 상태가 아래와 같을 것이다.

0  1  2  3  4  5  6  7  8  9  10  11  12  13 => 인덱스

0  0  1  0  1  1 -1 0  -1  0  -1   1    1   -2

 

이제 누적해서 더하면 아래와 같다.

0  1  2  3  4  5  6  7  8  9  10  11  12  13 => 인덱스

0  0  1  1  2  3  2  2  1  1   0    1   2    0

 

해당 날에 0이 아닌 경우 사각형 가로 길이를 증가시키고, 높이를 최대값으로 갱신하자.

해당 날이 만약 0이라면 사각형의 넓이를 계산하고 가로,세로 길이를 0으로 초기화하자.

 

from sys import stdin

input = stdin.readline

n = int(input())
board = [0]*(367)

for _ in range(n):
    s,e = map(int, input().split())
    board[s] += 1
    board[e+1] -= 1

def solv():
    max_height = 0
    length = 0
    answer = 0
    for idx in range(1,367):
        board[idx] += board[idx-1]
        if board[idx] == 0:
            answer += length * max_height
            max_height = 0
            length = 0
        else:
            max_height = board[idx] if max_height < board[idx] else max_height
            length += 1
    print(answer)

solv()