[백준 17371번] [Kotlin] 이사

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

17371번: 이사

 

난이도 : 골드 1
태그 : 그리디, 기하학

 

 

설명

다소 삽질을 좀 했던 문제였습니다.

가장 가까운 편의시설까지의 거리와 가장 먼 편의시설까지의 거리의 평균이 최소가 되는 좌표

가장 먼 편의시설까지의 거리는 잘 모르겠지만,

가장 가까운 편의시설까지의 거리는 사실 계산을 하는 로직이 필요하지 않습니다.

바로 편의시설과 집의 좌표가 같으면 거리가 항상 0입니다.

 

그럼 가장 먼 편의시설은 어떻게 구할까요?

그냥 한 편의 시설을 기준으로 다른 편의시설을 돌며 거리가 가장 먼 편의시설을 구하면 됩니다.

 

즉, 해당 문제는

한 점과 가장 거리가 먼 점을 찾으면서,

이 거리가 최소가 되는 쌍을 찾는게 핵심입니다.

 

 

 

 

소스코드

import java.util.StringTokenizer
import kotlin.math.pow
import kotlin.math.sqrt

data class Node(val x: Int, val y: Int)

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    val nodes = Array(n) {
        val st = StringTokenizer(readLine())
        Node(st.nextToken().toInt(), st.nextToken().toInt())
    }

    var min = Double.MAX_VALUE
    var idx = -1

    for (i in 0 until n) {
        var nowMaxDistance = -1.0

        for (j in 0 until n) {
            val distance = sqrt(
                (nodes[i].x - nodes[j].x).toDouble().pow(2) +
                        (nodes[i].y - nodes[j].y).toDouble().pow(2)
            )

            nowMaxDistance = maxOf(nowMaxDistance, distance)
        }

        if (min > nowMaxDistance) {
            min = nowMaxDistance
            idx = i
        }
    }

    println("${nodes[idx].x} ${nodes[idx].y}")
}

 

 

 

후기

로직은 사실 간단한 편이지만,

아이디어를 떠올리는게 굉장히 어려웠던 것 같습니다.

n이 그렇게까지 크지 않은 것 같은데, 모든 점에서 브루트포스를 돌려볼까? 싶었다가,

예제의 답이 정수가 아닌 걸 보고 바로 그만뒀습니다.

 

결국 구글링을 좀 하며 아! 가장 가까운 편의시설은 집과 편의시설이 같은 좌표일 경우구나!를 떠올려 풀긴 풀었으나,

고정 관념인지 집과 편의 시설이 같은 좌표에 있을 수 있다는 건 생각도 못했네요 ㅎㅎ;