이것저것 개발 블로그

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

문제)

풀이)

구현 문제인데 직사각형을 표현하는 방법을 어떻게 표현해야 할지 고민이 많았다. 결국 해결 못해서 이것저것 검색해봄..ㅎ

직사각형은 row, col을 구해야하므로 이를 생각해야 한다.

row는 어떤 날짜에 일정이 몇 개가 있는지에 따라 다르다. 이것은 문제에 있는 그림을 보면 이해하기 쉬울 것이다.

따라서 row를 구하기 위해 일정을 schedule이라는 일차원 배열에 저장한다. 여기에서 가장 큰 것이 row가 될 것이다.

col은 schedule에 저장한 값이 0이 아닌 것들이 연속된 개수이다. 따라서 schedule의 값을 확인하여 col 값을 구한다.

schedule 값이 0이라면 직사각형 하나가 만들어진 것이므로 row * col 값을 정답에 저장해준다.

이때, 만약 schedule의 맨 마지막 index인 365에서 0이 아닌 값이 존재한다면 정답에 row*col 값을 저장해 줄 수 없다.

따라서 이에 해당하는 조건을 달아 해결해준다.

소스코드)

n = int(input())
schedule = [0] * 366
for i in range(n):
    start, end = map(int, input().split())
    for j in range(start, end+1):
        schedule[j] += 1

row = 0
col = 0
answer = 0
for i in range(1, len(schedule)):
    if schedule[i] != 0:
        col += 1
        row = max(row, schedule[i])
    else:
        answer += row * col
        row = 0
        col = 0
    # 만약 맨 마지막에 일정이 존재한다면 정답에 업데이트가 되지 않는다. 따라서 새로운 if문 생성
    if i == len(schedule)-1:
        answer += row * col
print(answer)