[ 백준 ] 14658번 : 하늘에서 별똥별이 빗발친다 (파이썬)

문제 )

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

14658번: 하늘에서 별똥별이 빗발친다

 

[ 풀이 IDEA ]

1. N, M ≤ 500,000 이므로 트램펄린을 한칸씩 옮기는 Brute Force로는 문제를 해결할 수가 없다! 

2. 그러나, K<100이기 때문에 K를 이용해서 문제를 풀 것!

 

- python code 

def count_range(x, y):
    # 좌표가 범위 내에 있는지 확인
    star_cnt = 0
    for i in range(k):
        star_x, star_y = stars[i][0], stars[i][1]
        if (x<=star_x) and (star_x<=x+l) and (y<=star_y) and (star_y<=y+l):
            star_cnt += 1
    return star_cnt

def solution(n, m, l, k, stars):
    max_star = 0
    # 좌상단 좌표
    for i in range(k):
        # 우상단 좌표
        for j in range(k):
            x, y = stars[i][0], stars[j][1]
            # 해당 좌표가 범위 내에 있는지 확인
            max_star = max(max_star, count_range(x, y))
    return k - max_star


n, m, l, k = map(int, input().split())
# board = [[0]*(n+1) for _ in range(m+1)]
stars = []
for _ in range(k):
    star_xy = list(map(int, input().split()))
    stars.append(star_xy)

print(solution(n, m, l, k, stars))