[Kotlin, S4] 백준 16471번 작은 수 내기

출처: unsplash.com

 

작은 수 내기(16471번)

Silver 4

#그리디 알고리즘 #정렬

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

 

문제 내용

 

문제 접근

사장님이 뽑은 카드에서 이기기 위해 낼 수 있는 가장 큰 카드를 계속 냈을 때, 더 이상 이기는 수가 없을 경우, 이긴 횟수에 2를 곱해서 카드의 개수보다 크다면 YES를 출력하고, 아니면 NO를 출력하면 된다.

 

입력 예제를 예로 들면,

2 1 3 5 6
1 1 3 2 5

 

아래가 사장님의 카드고, 위가 주언의 카드일 때, 사장님이 카드를 큰 순서대로 뽑게 되면 5, 3, 2, 1, 1의 순서대로 뽑게 된다.

주언이 카드를 뽑아 사장님을 이기려면,

사장님이 5를 뽑았을 때, 5보다 작은 카드인 1, 2, 3 중에서 제일 큰 3을 고르고,

사장님이 3을 뽑으면 주언이는 2를,

사장님이 2를 뽑으면 주언이는 1을 뽑게 되면 먼저 3번을 이겼기 때문에 나머지 2판은 져도 최종적으로 이기게 된다.

 

결론

사장님이 뽑게 되는 카드에서 주언이 뽑아서 이길 수 있는 카드들 중 가장 큰 카드를 뽑는 것을 반복하면 된다.

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val n = bf.readLine().toInt()
    val me = bf.readLine().split(" ").map { it.toInt() }.toMutableList()
    val enemy = bf.readLine().split(" ").map { it.toInt() }.toMutableList()
    me.sort()
    enemy.sortDescending()

    var cardIndex = me.lastIndex
    var point = 0
    for (ei in 0 until enemy.size) {
        while (me[cardIndex] >= enemy[ei]) {
            cardIndex--
            if (cardIndex == -1) break
        }

        if (cardIndex == -1) {
            if (point * 2 > n) println("YES")
            else println("NO")

            return
        } else {
            me[cardIndex] = 100001
            point++
        }
    }

    println("YES")
}

 

문제 풀이

주언의 카드를 오름차순으로, 사장님의 카드를 내림차순으로 정렬한다.

그럼 사장님은 큰 카드부터 뽑게 된다.

주언이는 자신이 이길 수 있는 카드들 중 제일 큰 것을 뽑아서 이긴다.

한 번 쓴 카드는 100001로 변경해 주고, point를 늘려 준다.

이 과정을 반복하면 cardIndex가 -1이 되는데, 이 경우에는 모든 경우가 진다는 뜻이기 때문에 지금까지 이긴 point를 이용해 결과를 출력하고 return 한다.

 

return이 안 되는 경우는 주언이가 전승을 하는 경우이기 때문에 무조건 YES를 출력해야 한다.

 

 

문제 해결 과정

아이디어 자체를 떠올리는 것이 오래 걸리지 않아서 쉽게 해결한 문제이다.

아이디어를 떠올리는 것에서 개인차가 있을 수 있는 문제.

문제에 힌트가 있어서 아이디어를 떠올리는 게 쉬웠다.

체감 난이도: Silver 4