문제
수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다.
여름이 거의 끝나가자 장마가 시작되었고, 습기로 인해 달력에 표시한 일정이 지워지려고 한다. 지워지는 것을 막고자 수현이는 일정이 있는 곳에만 코팅지를 달력에 붙이려고 한다. 하지만 너무 귀찮았던 나머지, 다음과 같은 규칙을 따르기로 한다.
연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다.
연속된 모든 일정은 하나의 직사각형에 포함되어야 한다.
연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.
달력은 다음과 같은 규칙을 따른다.
일정은 시작날짜와 종료날짜를 포함한다.
시작일이 가장 앞선 일정부터 차례대로 채워진다.
시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.
일정은 가능한 최 상단에 배치된다.
일정 하나의 세로의 길이는 1이다.
하루의 폭은 1이다.
일정의 개수와 각 일정의 시작날짜, 종료날짜가 주어질 때 수현이가 자르는 코팅지의 면적을 구해보자
comment
생각보다 366이라는 숫자는 작은거임 ^^ 쨋든 10^3 보다 작자나?
(이 문제에서 입력의 개수도 10^3임) 이중for문 돌아도 10^6 보다 작음
보통 시간초과 날라면 10^9을 넘어야하는 거니까 굳이 막 투포인터, 힙 이딴걸로 풀겠다고 객기 안부려도 됨. 항상 이 악물고 시간좀 더 줄여볼 생각 먼저하니까 풀지도 못하고 시간만 낭비하는 듯
알고리즘에서 괜히 시간복잡도를 먼저 가르치는게 아님 대충 스쳐지나가서 비효율 적이라고 생각되도 계산 때려보고 되겠다 싶으면 걍하고 안 되겠다 싶으면 그때 시간을 줄일 수 있는 방법 or 알고리즘을 찾아가야겠음.
코드
N = int(input())
calendar = [0] * 366
for i in range(N):
s, e = map(int,input().split())
for j in range(s,e+1):
calendar[j] += 1
answer, width,height,now =0, 0, 0, 0
for i in range(366):
if calendar[i]:
width += 1
height = max(height,calendar[i])
else:
answer += width* height
width,height = 0,0
answer += width*height
print(answer)