브루트포스 - 14658번: 하늘에서 별똥별이 빗발친다

1) 초기 아이디어

: 격자 내에 트램펄린을 한 칸 씩 이동시키며 그 안에 별이 몇개 존재하는지 카운트하기 -> 시간초과 발생

2) 정답 아이디어

: 별 한 쌍의 좌표(하나는 가로 기준, 하나는 세로 기준으로 한 쌍)를 기준점으로 하여 트램펄린을 놓기 -> 별이 최소 1개 이상 있는 곳에만 트램펄린을 놓아보면서 탐색하는 것

line = list(map(int, input().split()))
n, m, l, k = line[0], line[1], line[2], line[3]

stars = []

for i in range(k):
    line = list(map(int, input().split()))
    stars.append((line[0], line[1]))

max_cnt = -1

for a, b in stars:
    for c, d in stars:
        x = c
        y = b

        cnt = 0
        for s1, s2 in stars:
            if x - l <= s1 <= x and y <= s2 <= y + l:
                cnt += 1

        max_cnt = max(max_cnt, cnt)

print(k - max_cnt)