20207 달력 파이썬 (재시도-0)

문제

 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 

여름이 거의 끝나가자 장마가 시작되었고, 습기로 인해 달력에 표시한 일정이 지워지려고 한다. 지워지는 것을 막고자 수현이는 일정이 있는 곳에만 코팅지를 달력에 붙이려고 한다. 하지만 너무 귀찮았던 나머지, 다음과 같은 규칙을 따르기로 한다.

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

달력은 다음과 같은 규칙을 따른다.

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

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

이때 코팅지의 크기의 합은 3 x 8 + 2 x 2 = 28이다. 

일정의 개수와 각 일정의 시작날짜, 종료날짜가 주어질 때 수현이가 자르는 코팅지의 면적을 구해보자.

입력

첫째 줄에 일정의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

둘째 줄부터 일정의 개수만큼 시작 날짜 S와 종료 날짜 E가 주어진다. (1 ≤ S ≤ E ≤ 365)

출력

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

 

 

참고 및 출처:
https://tmdrl5779.tistory.com/138

 

 

 

 

 

변수로는 n

s e

날짜 배열 [n][366]

명령어 배열 

이렇게 기본으로 했었다.

 

기본적인 풀이 방향으로

우선 입력받은 일정 명령어 배열을 정렬하는 걸 생각했다.

2차원 배열로 입력받는데, 규칙을 보면 같은 시작일에는 더 긴 날짜를

우선으로 하기 때문에, 시작일을 기준으로 오름차순으로 정렬후,

마지막날짜를 내림차순으로 정렬했다.

sort에서 옵션으로 key= lambda 를 이용해서 조건을 주었다.

 

그다음엔 일정을 입력하는건데, 이때는 리스트 슬라이싱을 이용했다.

하지만 자꾸 슬라이싱 부분에서 에러가 났다.

for문을 start,end in  이런식으로 뺐는데, 이부분 때문이었던것 같고,

인덱스에 직접접근하는 방식이 나았다.

 

마지막은 스티커 크기를 구하는 건데,

맨 바깥쪽은 1~365까지 열을 기준으로 했다.

그 열에서 아래로 행별로 쭉조사해서 일정이 1개라도 있으면 

직사각형의 세로를 +1시키는 방식이다. 가로의 경우 열을 하나씩 늘려나가면서

일정이 있으면 현재 가로값과 비교해서 최대값을 구하는 방식이다. 

다만 1이 없을 경우 띄어져 있으므로 현재까지의 직사각형 크기를 구해서 더해놓고,

가로세로를 초기화 한다.

 

 

풀이

 

#n입력
n=int(input())

calender=[[0]*366 for _ in range(n)]

todo=list()

for _ in range(n):
    #일정 입력받고 저장하기
    s ,e= map(int,input().split(' '))
    todo.append((s,e))

todo.sort(key=lambda x: (x[0], -x[1]))
# 시작일은 같은데 종료일이 더큰거 위치 변경하기

for k in range(len(todo)):
    s, e = todo[k][0], todo[k][1]

    for i in range(n):
        if 1 in calender[i][s: e + 1]:
            continue

        for j in range(s,e+1):
            calender[i][j] = 1
        break
#행 기억
row = 0
col = 0
ans = 0
# 정사각형 크기 구하기
for j in range(1,366):
    one_check=False
    for i in range(n):
        if calender[i][j] == 1:
            one_check = True
            row = max(row, i+1)
    if one_check:
        col+=1
    else:
        ans += row * col
        row = 0
        col = 0
if one_check:
     ans+= row * col

print(ans)