백준 14658 하늘에서 별똥별이 빗발친다 Kotlin (완전탐색)

문제 출처 : https://www.acmicpc.net/problem/14658

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)

출력

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

알고리즘 분류

• 브루트포스 알고리즘

풀이

무슨 생각으로 n*m 사이즈 2차원 배열을 만들고 있었지?

배열은 만들 수도 없고 당연히 n*m만큼 완전 탐색을 할 수도 없다.(메모리 초과, 시간 초과)

다른 분의 풀이를 참고하여 풀었다.

참고하여 풀었는데 코드가 같아졌다.

 

어찌 됐건 풀이를 설명하자면, 3중 포문으로 해결할 수 있다.

바깥의 2중 포문은 범위를 설정하는 것이고, 안의 포문은 범위 내에 별의 개수를 구하는 것이다.(트램펄린에 튕길 별)

https://astrid-dm.tistory.com/463  

범위를 설정하는 것은 위의 글을 읽으면 이해가 될 것이다.

덧붙이자면, (1,1)와 (5,5)의 좌표가 있고 l이 4일 때 2중 포문으로 사분면의 범위가 탐색되는 경우는 다음과 같다.

(1,1), (1,1) = 1사분면

(5,5), (1,1) = 2사분면

(1,1), (5,5) = 3사분면

(5,5), (5,5) = 4사분면

아래 코드에서 x가 star[i].first, y가 star[j].second인 이유이다.

코드

val br = System.`in`.bufferedReader()

//1 <= n,m <= 500000 그래프 가로 세로
//1<= l <= 100000 트램펄린 길이
//1< k < =100 별똥별 수

fun main() = with(System.out.bufferedWriter()){

    val (m,n,l,k) = br.readLine().split(' ').map{it.toInt()}
    val star = Array(k){Pair(0,0)}
    for(i in 0 until k){
         br.readLine().split(' ').map{it.toInt()}.also{star[i] = Pair(it[0],it[1])}
    }
    var answer =0
    for(i in 0 until k){
        val x = star[i].first
        for(j in 0 until k){
            val y = star[j].second
            var sum=0
            for(a in 0 until k){
                val cX = star[a].first
                val cY = star[a].second
                if(x<= cX && cX <=x+l && y <= cY && cY <= y+l) sum++
            }
            answer = answer.coerceAtLeast(sum)
        }
    }
    write("${k-answer}")
    close()
}