BOJ 2669. [Silver5] 직사각형 네개의 합집합의 면적 구하기

[hojongs]

Problem link

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

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

Pseudo-code

idea를 수도 코드로 작성해본다

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

Impl

import sys

readl = sys.stdin.readline

squares = [[int(i) for i in readl().split()] for _ in range(4)]

def f():
    """
    area = 0
    모든 좌표를 순회
        if 좌표 in any squares: area += 1
    """
    area = 0
    for ri in range(1, 100):
        for ci in range(1, 100):
            for c0, r0, c1, r1 in squares:
                if r0 <= ri < r1:
                    if c0 <= ci < c1:
                        area += 1
                        break
    print(area)

f()

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

50분? 다른 아이디어를 너무 오래 고민함

더 빠른 알고리즘 (분기문 없이, 중복 비교도 없이)

https://www.acmicpc.net/source/8979413

구현력: 알고리즘을 신속, 정확하게 구현했는가?