BOJ_20207 : 달력

👉 문제링크

20207번: 달력

---

---

🔸 문제 분석 🔸

• 규칙에 따라 달력에 일정이 표시된다.
• 이어진 일정들의 높이와 너비를 곱해 면적을 구하고, 면적들의 총 합을 출력하면 된다.

🔸 코드 🔸

import sys
input = sys.stdin.readline
print = sys.stdout.write

N = int(input())
cal = []            # 입력된 일정 리스트
calmap = [0]*366    # 일정을 표시할 달력

for i in range(N):  # 일정 입력
    S, E = map(int, input().strip().split())
    cal.append((S,E))

# 시작 일이 빠르고, 기간이 길수록 앞쪽으로 정렬
cal = sorted(cal, key = lambda x : (x[0], -x[1]))

for s, e in cal:    # 달력에 일정 표시
    for i in range(s,e+1):
        calmap[i] += 1

answer = 0
w = 0   # 임시 너비
h = 0   # 임시 높이
flag = False     # 코팅지 너비 체크 중 여부
for i in calmap: # 달력 확인
    if flag:        # 코팅지 너비 확인 X
        if i != 0:  # 코팅지 너비 확인 시작
            flag = True
            w += 1
            h = i
    else:           # 코팅지 너비 확인중
        if i == 0:  # 코팅지 너비 확인 종료
            flag = False
            answer += w*h
            w = 0
            h = 0
        else:
            if i > h:
                h = i
            w += 1
            
answer += w*h # 코팅지 너비 확인 중 종료됐을때 남은거 더해주기

print(str(answer))

🔸 코드 해석 🔸

• 달력을 1차원 리스트로 표현했다.
• 입력된 일정을 2가지 기준으로 정렬해 달력에 표시하면 규칙을 지키며 표현할 수 있다.
• 일정이 끝나지 않고 달력이 끝나는 경우를 대비해 마지막에 한번 더 더해준다.

---

🔸 end 🔸

• 실버 1문제지만 아이디어 구상이 잘 되어, 크게 어렵지 않게 풀은 것 같다.
• 2가지 조건의 정렬 방법이 기억나지 않아 검색해서 사용했다.
• 그리디 알고리즘의 문제라는데 신경쓰지 않고 풀었다. 따지고 보면 조건에 맞게 일정을 달력에 써야하니 그리디가 맞는 것 같다.