사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
E U S​ E W
 
ps/problems/boj/2190.txt · 마지막으로 수정됨: 2023/09/25 09:03 저자 teferi