본문 바로가기

기하학1

[Python] 백준 1186 직사각형 색칠하기 문제 링크 : https://www.acmicpc.net/problem/1186 1186번: 직사각형 색칠하기 2차원 좌표 평면에 변이 축에 평행한 직사각형 N개가 있다. 직사각형은 1부터 N까지 번호가 매겨져 있다. i번 직사각형의 왼쪽 아래 꼭짓점의 좌표는 (xi,1, yi,1)이고, 오른쪽 위 꼭짓점의 좌표는 (xi www.acmicpc.net 1. 접근 방법 어떻게든 그리디 한 방법이나, 스위핑 같은 방법을 고민했는데, 여러 직 사각형이 겹치는 경우의 해결 방법이 떠오르지 않아, 전체 탐색을 고민했다. 최대 50개 직사각형을 탐색해서 50 * 50으로 각 직사각형마다 겹치는지 확인할 수 있고, 각 직사각형이 최대로 많이 탐색해도 50 * 8 정도라 생각하여 최대 1,000,000번의 탐색으로 가능.. 2021. 11. 1.

티스토리툴바