ps:problems:boj:2190
점 고르기 2
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 2190 |
문제명 | 점 고르기 2 |
레벨 | 골드 4 |
분류 |
브루트포스 |
시간복잡도 | O(n^3) |
인풋사이즈 | n<=100 |
사용한 언어 | Python 3.11 |
제출기록 | 31256KB / 120ms |
최고기록 | 120ms |
해결날짜 | 2023/09/25 |
풀이
- 효율적으로 풀어야 한다면, 스위핑과 좌표압축과 레이지 세그먼트 트리 (구간 합 update + 구간 max 쿼리) 를 이용하는 전형적인 방식의O(nlogn)풀이를 쉽게 떠올릴수 있다. 하지만 접근방식이 전형적이지 구현이 간단하다는 말은 아니다..
- n의 제한이 100밖에 안되니까 풀이가 좀 비효율적이어도 상관없다. 간단하게 구현할수 있는 방법은 다음과 같다.
- 가장 많은 점을 포함하는 사각형을 찾는 것은, 왼쪽변에 겹치는 점이 존재하고, 위쪽변에도 겹치는 점이 존재하는 사각형들로 후보를 좁혀도 상관 없다. (가장 많은 점을 포함하는 사각형이 왼쪽 변에 겹치는 점을 포함하지 않는다면, 그 사각형을 왼쪽변에 겹치는 점이 생길때까지 오른쪽으로 평행이동 시켜도 포함하는 점의 갯수는 줄어들지 않으므로, 여전히 가장 많은 점을 포함하는 사각형이 된다)
- 그러면 주어진 점들중에서 2개를 뽑아서 하나를 왼쪽변, 하나를 위쪽 변에 놓는다고 생각하면 총 사각형의 후보를 n^2개로 줄일수 있다. 각 사각형이 몇개의 점을 포함하는지도, 그냥 n개의 점에 대해서 다 체크하면, 총 O(n^3)에 가장 많은 점을 포함하는 사각형을 찾을수 있다.
코드
"""Solution code for "BOJ 2190. 점 고르기 2".
- Problem link: https://www.acmicpc.net/problem/2190
- Solution link: http://www.teferi.net/ps/problems/boj/2190
Tags: [brute force]
"""
def main():
N, A, B = [int(x) for x in input().split()]
coords = [[int(x) for x in input().split()] for _ in range(N)]
answer = 0
for left, _ in coords:
for _, top in coords:
count = sum(
1
for x, y in coords
if left <= x <= left + A and top <= y <= top + B
)
answer = max(answer, count)
print(answer)
if __name__ == '__main__':
main()
ps/problems/boj/2190.txt · 마지막으로 수정됨: 2023/09/25 09:03 저자 teferi
토론