[ 백준 2473 ] - 세 용액 (Kotlin)

 

 

2473번: 세 용액

 

먼저 풀어보면 좋을 문제

2467번: 용액

 

문제 이해 & 기본 개념

• 세 용액의 합이 최소가 되는 경우를 구하는 문제
• 용액(2467번) 문제에서 하나의 용액이 더 추가 되었다.
• 용액(2467번) 문제는 투 포인터로 쉽게 풀 수 있었지만, 해당 문제는 3개의 용액을 더 해야하므로 단순 투 포인터로는 힘들 듯하다.

---

중요 포인트

• 투 포인터를 유지하되, 3개의 용액을 더하는 방법을 찾아야 함
• 1가지의 용액을 고정한 후, 나머지 용액에 대해서 투 포인터를 수행하면 됨 ( 용액(2467번) 문제와 동일해짐 )

 

---

최종 풀이

• 첫 용액부터 하나씩 고정 선택 값으로 지정한다.
• 하나를 골랐으므로, 나머지 용액들에 대해선 투 포인터를 수행
• 고정 용액 + 나머지 두 용액의 합의 최솟값을 체크하면 됨
• 앞에서부터 차례대로 고정 용액을 선택하고, 그 이후 용액들에 대해 투 포인터를 수행하므로 오름차순이 보장 됨

---

 

주의 할 점

• 용액의 최대 개수는 5,000개이며, 각 용액의 값은 -1,000,000,000 ~ 1,000,000,000 까지 이므로, Int 범위를 벗어날 수 있음에 주의

---

 

소스 코드

import kotlin.math.abs

fun solve(n: Int, num: List<Long>): Triple<Long, Long, Long> {
    var min:Long = Long.MAX_VALUE
    var minLiquid = Triple(num[0], num[1], num[2])

    // 고정으로 하나를 골라 놓고, 나머지 값들에 대해 투 포인터 수행
    for (pick in 0 until n) {
        var s = pick + 1
        var e = n - 1

        while (s < e) {
            val cur:Long = num[pick] + num[s] + num[e]

            if (abs(min) > abs(cur)) {
                min = cur
                minLiquid = Triple(num[pick], num[s], num[e])
            }

            // 뒤로 갈수록 커지므로 음수일 땐 s를 당기고
            // 양수이면 e를 당김
            if (cur < 0) s++
            else e--
        }
    }

    return minLiquid
}

fun main() {
    val n = readln().toInt()
    val list = readln()
            .split(" ")
            .map { it.toLong() }
            .toList()
            .sorted()

    val result = solve(n, list)
    println("${result.first} ${result.second} ${result.third}")
}