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

 

백준 14658번

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

 

브루트포스, 라고는 나와있는데 구글링 했을 때랑 다르게 풀었음

K의 갯수가 100개 이하이므로 K기준으로 진행

 

---

12 10 4 7
2 4
7 3
3 1
5 6
4 7
12 10
8 6

해당 예제에서 별의 위치를 받고, 얘네를 우선 x기준으로 정렬을 해준다.

 

[(2, 4), (3, 1), (4, 7), (5, 6), (7, 3), (8, 6), (12, 10)]

이런식으로 x기준으로 정렬을 한 다음 앞에서부터 한개씩 뽑아서 

x에 L을 더한 거에 범위안에 들어가는 것들을 뽑아서 다시 행렬을 만든다

 

예를 들어, (2, 4)기준으로 보면 여기서 L이 4니까 2가 가장 왼쪽이라면 x의 최대값은 이 점의 x좌표인 2와 L의 합인 6이 될것이다. 이렇게 되면 위의 행렬에서 (7, 3)이후의 점들은 빠지게되고, x기준으로 가능한 애들을 빼서 따로 행렬을 만들어준다.

[(2, 4), (3, 1), (4, 7), (5, 6)]

그 다음에, 이 행렬을 y기준으로 sort를 해준다.

 

[(3, 1), (2, 4), (5, 6), (4, 7)]

 

그 다음에, 아까랑 똑같이 처음 점부터 y에 L을 더해서 그 안에 있는 애들만 필터링해준다.

 

이렇게 돌려서 가장 최대값이 되는 것을 저장하면서 진행하면 끝!

 

---

전체 코드

# 하늘에서 별똥별이 빗발친다

N, M, L, K = map(int,input().split())
stars = []
for _ in range(K):
  a, b = map(int, input().split())
  stars.append((a, b))

# x 기준으로 정렬
stars.sort()
# [(2, 4), (3, 1), (4, 7), (5, 6), (7, 3), (8, 6), (12, 10)]

ans = 1

for i in range(K - 1):
  temp = [stars[i]]
  for j in range(i + 1, K):
    if stars[j][0] <= stars[i][0] + L:
      temp.append(stars[j])
  # 이걸 다시 y기준으로 정렬해서
  temp.sort(key=lambda x: x[1])
  maxcnt = 1
  for p in range(len(temp) - 1):
    cnt = 1
    for q in range(p + 1, len(temp)):
      if temp[q][1] <= temp[p][1] + L:
        cnt += 1
    if cnt > maxcnt:
      maxcnt = cnt
  if maxcnt > ans:
    ans = maxcnt
print(K - ans)