[백준] 14658 하늘에서 별똥별이 빗발친다, python

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

 

 

 

 

 

 

트램펄린을 놓을 수 있는 모든 경우에 수에 대해 별똥별이 해당 범위 내에 포함되는지 여부를 체크하여 개수를 세어주면 된다.

 

 

 

import sys
input = sys.stdin.readline


n, m, l, k = map(int, input().split())
# 별똥별이 떨어질 수 있는 모든 x좌표와 y좌표를 set으로 저장
pos_x = set()
pos_y = set()
star = []
for _ in range(k):
    x,y = list(map(int, input().split()))
    pos_x.add(x)
    pos_y.add(y)
    star.append([x,y])

answer = 0

# 트램펄린의 왼쪽 위 좌표를 sx,sy로 설정
for sx in pos_x:
    for sy in pos_y:
        cnt = 0
        # 별똥별이 해당 범위에 있는지 체크
        for x,y in star:
            if sx<=x<=sx+l and sy<=y<=sy+l:
                cnt += 1
        answer = max(answer,cnt)

print(k-answer)