[백준] 20207번 (python 파이썬)

https://www.acmicpc.net/problem/20207

 

구현문제이다.

 

일정이 이렇게 있다면

코팅지를 붙여야 하는 영역은

 

 

이 부분이다.

 

즉 겹치는 부분의 row최대와 col의 최대를 구하고 곱해준다음 결과값에 계속 더해준다.

 

우선 2차원 배열로 캘린더를 만들어줬다.

 

해당 col의 row를 먼저 확인하고 다 확인했으면 다음 col로 넘어간다.

row의 최대값을 구한다. col은 날짜가 넘어갈때마다 1씩 더해준다.

해당 일에 일정이 있어야한다.

row 값

2일 일때 : 1

3일 일때 : 1

4일 일때 : 2

5일 일때 : 3

6일 일때 : 3

7일 일때 : 2

8일 일때 : 2

9일 일때 : 2

10일에는 일정이 없다.

일정이 없을때는 이전까지 구한 row 와 col을 계산해준다.

row x col = 3 x 8 = 24

 

11일 일때 : 1

12일 일때 : 2

row x col = 2 x 2 = 4

 

답 : 24 + 4 = 28

 

n = int(input())

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

todo = list()

for _ in range(n):
    s, e = map(int, input().split(' '))
    term = e - s + 1
    todo.append((s, e, term))

todo.sort(key=lambda x: (x[0], -x[2]))

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)

 

 

최적화

 

2차원 배열로 캘린더를 만들지 않고

1차원 배열만 이용하여 해당 날짜에 일정이 몇개 있는지 넣어줬다. 이 개수는 row의 개수가 된다.

일정이 0개 있는날을 기준으로 row x col을 구한다

n = int(input())
canlender = [0] * 366

for _ in range(n):
    s, e = map(int, input().split(' '))

    for i in range(s, e + 1):
        canlender[i] += 1

row = 0
col = 0
ans = 0
for i in range(366):
    if canlender[i] != 0:
        row = max(row, canlender[i])
        col += 1
    else:
        ans += row * col
        row = 0
        col = 0
ans += row * col
print(ans)