[백준 1007] 벡터 매칭

백준 1007번: 벡터 매칭 - Kotlin 최적화 풀이 🚀

1. 문제 소개 📝

백준 1007번 "벡터 매칭" 문제는 N개의 점을 사용해 벡터를 만들고, 모든 벡터의 합의 길이를 최소화하는 문제입니다.

🔹 입력 형식

• 첫 번째 줄: 테스트 케이스 개수 T
• 각 테스트 케이스:
  • 첫 번째 줄: 점의 개수 N (항상 짝수)
  • 다음 N개 줄: 각 점의 x, y 좌표

🔹 출력 형식

각 테스트 케이스에 대한 벡터 합의 최소 길이를 출력합니다.

2. 문제 해결 접근법 💡

문제의 핵심은 N개의 점을 짝지어 벡터를 만들고, 벡터 합의 길이를 최소화하는 것입니다.

🔹 기본적인 해결 방법

• 단순한 순열(Brute-force) 접근은 O(N!)의 시간 복잡도로 매우 비효율적입니다.
• 조합(combinations)을 사용한 최적화 방법을 적용하여 O(2^N)으로 개선할 수 있습니다.
• 벡터의 합은 선택된 점을 빼고, 선택되지 않은 점을 더하는 방식으로 계산하면 빠르게 해결할 수 있습니다.

3. Kotlin 코드 구현 💻

import kotlin.math.sqrt
import kotlin.math.min
import kotlin.math.pow

fun main() {
    val t = readLine()!!.toInt()
    repeat(t) {
        solve()
    }
}

fun solve() {
    val n = readLine()!!.toInt()
    val points = Array(n) { Pair(0, 0) }
    var sumX = 0
    var sumY = 0
    
    for (i in 0 until n) {
        val (x, y) = readLine()!!.split(" ").map { it.toInt() }
        points[i] = Pair(x, y)
        sumX += x
        sumY += y
    }
    
    val indexList = (0 until n).toList()
    var minLength = Double.MAX_VALUE
    
    fun combination(start: Int, count: Int, selected: List) {
        if (count == n / 2) {
            var xDiff = sumX
            var yDiff = sumY
            
            for (idx in selected) {
                xDiff -= 2 * points[idx].first
                yDiff -= 2 * points[idx].second
            }
            
            minLength = min(minLength, sqrt(xDiff.toDouble().pow(2) + yDiff.toDouble().pow(2)))
            return
        }
        
        for (i in start until n) {
            combination(i + 1, count + 1, selected + i)
        }
    }
    
    combination(0, 0, emptyList())
    println(minLength)
}

4. 코드 설명 🧐

1. 입력 처리:

   readLine()을 사용하여 입력을 받고, split()과 map()을 활용해 좌표를 저장합니다. 전체 좌표의 x, y 값의 합(sumX, sumY)을 미리 계산합니다.

2. 조합(combinations) 활용:

   재귀 함수를 사용해 n/2개의 점을 선택하는 조합을 생성합니다. 선택된 점들은 벡터의 시작점, 나머지 점들은 벡터의 끝점으로 취급합니다.

3. 벡터 합 길이 최소화:

   선택된 점들의 좌표를 이용해 벡터 합의 길이를 계산합니다. sqrt(xDiff² + yDiff²)을 사용하여 최단 거리 값을 갱신합니다.

5. 성능 분석 ⏱️

접근법	시간 복잡도
완전 탐색(Brute-force)	O(N!)
조합 최적화	O(2^N)

Brute-force 방식은 N이 커질수록 실행 시간이 기하급수적으로 증가합니다. 조합을 활용한 접근법은 효율적으로 계산하며, N ≤ 20인 문제 조건에서는 충분히 빠르게 동작합니다.

6. 결론 🎯

이 문제는 조합론적 사고가 필요한 문제입니다. 순열을 활용한 완전 탐색 대신 조합을 사용한 최적화 기법을 적용하여 성능을 크게 개선할 수 있습니다. Kotlin에서 재귀 조합 함수를 활용하여 효율적으로 해결할 수 있습니다. 🚀

다음에도 백준 알고리즘 문제 해결을 계속 공유할 예정이니, 기대해주세요! 😉