[백준 1715번] [Kotlin] 카드 정렬하기

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

1715번: 카드 정렬하기

 

난이도 : 골드 4
태그 : 자료 구조, 그리디 알고리즘, 우선순위 큐

 

 

1. 설명

비교 횟수가 최소가 되려면

매번 가장 작은 개수의 카드 묶음 두개씩 비교하여 합치면 됩니다.

 

매번 정렬하여 가장 작은 값 두개를 찾을 필요 없이,

우선순위 큐를 사용하면 쉽게 구할 수 있습니다.

 

 

 

2. 소스코드

      

      

      

    
    

      <kotlin />
    
import java.util.PriorityQueue

fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    
    val cards = PriorityQueue<Int>()

    repeat(n) {
        cards.add(br.readLine().toInt())
    }

    var total = 0

    while (cards.isNotEmpty()) {
    	// 큐에서 카드 하나 꺼냄
        val a = cards.poll()
        // 큐가 비어있지 않으면 카드를 하나 더 꺼내서 비교함
        if (cards.isNotEmpty()) {
            val sum = a + cards.poll()
            total += sum
            cards.add(sum)
        }
    }

    println(total)
}

 

 

 

3. 후기

매번 최적의 해(가장 작은 값 두 개)를 선택하는 그리디 알고리즘 입니다.

두 개의 카드를 선택해 합치고, 매번 정렬하여 가장 작은 값 두 개를 찾아야 하나 싶었는데,

우선순위 큐를 이용하면 꽤 쉽겠다 생각하여 우선순위 큐를 사용해 풀이하였습니다.