[백준/Kotlin] 하늘에서 별똥별이 빗발친다(14658)

문제

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

 

“오빠! 나 얼마만큼 사랑해?”

“널 위해서라면 저기 저 하늘의 별이라도 따다 줄 수 있어. 지금 따줄까?”

“에이, 거짓말!”

“정말이야. 한 번 봐봐!”

욱제는 하늘을 발로 차버렸다. 그랬더니 정말 별이 떨어졌다. 그런데, 정말로 별이 지구로 떨어지기 시작했다. 욱제는 지구를 지키는 정의의 용사가 되기로 결심했다.

“자기야, 나 세계를 지키고 올게. 꼭 돌아올 테니 조금만 기다려줘.”

지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 L*L 크기의 트램펄린을 준비했다. 별똥별이 어디로 떨어질지는 이미 알고 있기 때문에, 욱제는 이 트램펄린으로 최대한 많은 별똥별을 우주로 튕겨낼 계획이다. 하지만 학교 예산으로 트램펄린을 구매하는 욱제는 이 긴급한 와중에도 예산 심의 통과를 기다리느라 바쁘다!

욱제를 도와 세계를 구하자. 최대한 많은 별똥별을 튕겨내도록 트램펄린을 배치했을 때, 지구에는 몇 개의 별똥별이 부딪히게 될까? (별똥별이 떨어지는 위치는 겹치지 않으며 별똥별은 트램펄린의 모서리에 부딪혀도 튕겨나간다!) 트램펄린은 비스듬하게 배치 할 수 없다.

 

[ 입력 ]

첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 뜻한다. 이후 K개의 줄에 걸쳐 별똥별이 떨어지는 위치의 좌표 (x, y)가 주어진다. (0 ≤ x ≤ N, 0 ≤ y ≤ M)

 

[ 출력 ]

욱제가 트램펄린으로 최대한 많은 별똥별을 튕겨낼 때, 지구에 부딪히는 별똥별의 개수를 출력한다.

 

---

풀이

 

- 처음에는 공간 크기만큼 배열을 생성해서 완전탐색을 했더니 메모리 초과로 실패했다.

- 두번째는 배열은 생성하지 않았지만 마찬가지로 트램펄린을 모든 위치에 놓아보는 완전탐색을 해서 시간초과로 실패

- 그리고 트램펄린에 튕기는 별똥별 개수를 반환하는 건 줄 알고 있다가 바닥에 떨어지는 개수라는 걸 중간에 알아챘다...

- 메모리, 시간을 초과하지 않으려면 별똥별 수가 100개 이하라는 것을 포인트로 잡고 풀어내야한다.

- 별똥별 위치를 기준으로 나올 수 있는 경우의 수를 테스트 해보면 되는데, 한 위치를 트램펄린의 좌상단으로 잡고 계산하면 되지 않을까? 했지만 그렇게 하면 모든 경우의 수를 고려해볼 수 없게 된다.

- 별똥별 2개가 모서리에 위치하게 정사각형을 만들어보면 정상적으로 계산이 되는 걸 볼 수 있었다.

// 백준 - 하늘에서 별똥별이 빗발친다(14658)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.max
import kotlin.math.min

data class Star(
  var x: Int,
  var y: Int
)

var N = 0
var M = 0
var L = 0
var K = 0
var star: Array<Star> = arrayOf()

fun main() {
  val br = BufferedReader(InputStreamReader(System.`in`))
  var st = StringTokenizer(br.readLine())

  var maxStar = 0 // 떨어지는 별똥별 최대값

  N = st.nextToken().toInt() // 가로
  M = st.nextToken().toInt() // 세로
  L = st.nextToken().toInt() // 트램펄린 한 변의 길이
  K = st.nextToken().toInt() // 별똥별의 수

  star = Array(K, {Star(0, 0)}) // 별똥별이 떨어지는 위치

  for(i: Int in 0..K-1) {
    st = StringTokenizer(br.readLine())
    star[i].x = st.nextToken().toInt()
    star[i].y = st.nextToken().toInt()
  }

  for(i: Int in 0..K-1) {
    for(j: Int in 0..K-1) {
      // 두 별똥별을 거치는 가장 큰 사각형 범위
      // 트램펄린 내부에 들어갈 수 있는 개수 체크
      // 좌상단 좌표 
      var startX = min(star[i].x, star[j].x)
      var startY = min(star[i].y, star[j].y)
      // 우하단 좌표
      var finX = startX + L
      var finY = startY + L

      var cnt = 0 // 트램펄린 위에 떨어진 별똥별

      for(k: Int in 0..K-1) {
        // 트램펄린 범위 안에 떨어지는 별똥별 체크
        if(star[k].x >= startX && star[k].x <= finX && star[k].y >= startY && star[k].y <= finY) {
          cnt++
        }
      }

      maxStar = max(maxStar, cnt)
    }
  }

  // 튕겨낸 별똥별을 제외하고 지구에 부딪히는 별똥별의 개수
  print(K - maxStar)
}