백준 15728 에리 - 카드 Kotlin (완전탐색)

문제 출처 : https://www.acmicpc.net/problem/15728

15728번: 에리 - 카드

문제

2468년 개최된 해왕성 올림픽, ‘에리 - 카드’는 드디어 올림픽 정식 종목으로 채택된다. ‘에리 - 카드’는 N 장의 ‘공유 숫자카드’와 N 장의 ‘팀 숫자카드’를 받고 시작한다. 상대 팀은 우리 팀의 ‘팀 숫자카드’ K 장을 견제할 수 있는데, 견제된 카드는 낼 수 없게 된다. 모든 견제가 마친 후 우리 팀은 ‘공유 숫자카드’에서 한 장, ‘팀 숫자카드’ 중 한 장씩을 골라 내게 되는데, 두 카드의 곱이 우리 팀의 점수가 되며 이후 같은 방식으로 상대 팀도 진행하여 상대 팀의 점수보다 높을 경우 이기게 된다.

상대팀은 항상 최선의 방법으로 N장의 우리 팀의 ‘팀 숫자카드’ 중 K장을 견제한다고 했을 때, 우리 팀이 얻을 수 있는 최대 점수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N, K(0 ≤ K < N ≤ 100)가 주어지고 둘째 줄에는 N개의 ‘공유 숫자카드’에 적혀 있는 정수, 셋째 줄에는 N개의 ‘팀 숫자카드’에 적혀 있는 정수가 주어진다. 이 수는 -10,000보다 크거나 같고, 10,000보다 작은 정수이다.

출력

우리 팀이 얻을 수 있는 최대 점수를 출력한다.

힌트

상대팀은 ‘팀 숫자카드’ 2장의 카드를 견제 할 수 있고 가장 큰 점수가 나올 수 있는 카드 4와 카드 3을 견제할 것이다. 이후 남은 카드로 이 팀은 ‘공유 숫자카드’의 카드 5와 ‘팀 숫자카드’의 카드 2로 최대 10점을 얻을 수 있다.

알고리즘 분류

• 구현
• 브루트포스 알고리즘

풀이

간단한 완전 탐색 문제.

팀 숫자 카드 리스트에서 k개만큼 제거할 수 있다.

이때 제거할 k 개의 카드는 상대편 입장에서 최선의 카드만 제거한다.

이 말은 내가 상대 편의 팀 숫자 카드를 k개 제거해서 상대 팀이 공유 숫자 카드와 팀 숫자 카드를 곱한 결과 중 가장 큰 값이 최소가 되게끔 해야 한다는 말이다.

여기서 중요한 점은 카드에 음수가 들어갈 수 있다는 점.

팀 숫자카드에 음수, 공유 숫자카드에 음수라면 두 카드를 곱했을 때 양수가 나온다.

그럼 단순히 팀 숫자카드에서 가장 높은 값 k개를 제거하는 것은 최선이 아닐 수 있다.

위의 예시에서 팀 숫자카드, 공유 숫자카드의 음수값이 -1,-1이 아니라 -30, -20이라면 600이 나올 수 있기 때문이다.

따라서 일단 팀 숫자카드와 공유 숫자카드를 모두 곱한다.

그리고 이를 정렬하여 가장 큰 값부터 팀 숫자카드 k개를 삭제하면 된다.

위의 입력을 예시로 들면,

5 * 4 = 20

4 * 4 = 16

5 * 3 = 15

5 * 2 = 10  

4와 3이라는 팀 숫자 카드 두 개를 삭제하고 2를 사용한 5*2 = 10이 정답이 된다.

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }

data class Node(
    val result: Int,
    val card: Int,
)

fun main() = with(System.out.bufferedWriter()) {

    //input
    val (n, k) = getIntList()
    val shareCards = getIntList()
    val teamCards = getIntList()
    
    //solve
    val nodeList = ArrayList<Node>()
    shareCards.forEach {
        teamCards.forEach { card ->
            nodeList.add(
                Node(
                    it * card,
                    card
                )
            )
        }
    }
    nodeList.sortByDescending { it.result }
    var removeCnt = 0
    val removeSet = mutableSetOf<Int>()
    var answer = 0
    for((result,card) in nodeList){
        if(!removeSet.contains(card)){
            if(removeCnt == k){
                answer = result
                break
            }
            removeSet.add(card)
            removeCnt++
        }
    }
    //output
    write("$answer")
    close()
}