[백준] 1744번 수 묶기

백준 - 1744번 수 묶기

문제

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(23)+(45) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

접근 방법

각 수가 최대가 되는 경우를 찾는 방법
a > 1 && b > 1 인경우 곱했을 때 더한 것보다 커지므로 묶기
a < 1 && b < 1 인 경우 곱했을 때 더한 것보다 커지므로 묶기

따라서, sortDescending을 한 후에 양수의 경우와 둘다 1보다 작은 경우를 절댓값이 큰 경우부터 확인하며 더해서 넣어준 뒤
미처 넣지 못한 부분을 추가로 넣음으로써 문제를 해결하였다.

코드

import java.lang.Math.hypot
import java.util.*

class IO1774 {
    private val br = System.`in`.bufferedReader()
    private val bw = System.out.bufferedWriter()

    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
    fun getRow() = br.readLine().split(" ").map{ it.toInt() }
}

fun main() {
    val io = IO1774()
    val (N, M) = io.getRow()

    fun getArray(num: Int): Array<List<Int>> {
        return Array(num) {
            io.getRow()
        }
    }

    val positionArr = getArray(N)
    val distanceArr = Array(N) { Array(N) { Double.MAX_VALUE } }

    fun getDistance(p1: List<Int>, p2: List<Int>): Double {
        val (x1, y1) = p1
        val (x2, y2) = p2
        return hypot((x1-x2).toDouble(), (y1-y2).toDouble())
    }

    for (i in 0 until N) {
        val p1 = positionArr[i]
        for (j in i+1 until N) {
            val p2 = positionArr[j]
            val dis = getDistance(p1, p2)
            distanceArr[i][j] = dis
            distanceArr[j][i] = dis
        }
    }

    val visited = Array(N) { false }

    repeat(M) {
        val (p1, p2) = io.getRow()
        distanceArr[p1-1][p2-1] = 0.0
        distanceArr[p2-1][p1-1] = 0.0
    }

    data class Edge(val source: Int, val dest: Int, val cost: Double)
    val pq = PriorityQueue<Edge>(compareBy { it.cost })
    for(row in 1 until N) {
        pq.add(Edge(0, row, distanceArr[0][row]))
    }
    var answer: Double = 0.0
    var edge = 0
    visited[0] = true
    while (edge < N - 1) {
        val e = pq.poll()
        val (sour, dest, cost) = e

        if (visited[dest]) continue
        visited[dest] = true
        answer += cost
        edge++

        if (cost == Double.MAX_VALUE) continue

        for (row in 0 until N) {
            if (dest == row) continue
            pq.add(Edge(dest, row, distanceArr[dest][row]))
        }
    }
    io.write(String.format("%.2f", answer))
    io.close()
}