[백준] [02798] [코틀린] 블랙잭

문제

• 플랫폼 : 백준
• 번호 : 02798
• 제목 : 블랙잭
• 난이도 : Bronze 2
• N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력
• 문제 : boj2798

 

생각

1. 합을 구해야하는데 3개 숫자를 선택해서 반복을 돌려야하므로 배열에 저장해야한다.

2. 배열의 서로 다른 인덱스에 위치한 숫자 3개를 선택하려면 3중 for문을 돌려야할 것이다. 이렇게 숫자 3개를 구하고 모두 합하는 작업을 반복할 경우 시간복잡도가 O(N3)까지 갈 듯 하다.

3. 반복문을 돌리는 것은 피할 수 없다.하지만 불필요한 반복을 줄일 수 있진 않을까?

4. 3중 반복문을 돌 때 첫번째 반복문, 두번째 반복문 시점에서 여태까지 합산한 값이 m보다 크면 거기서부터는 더 숫자를 합해봐야 무조건 m보다 크므로 더 따지지 않고 다음 반복으로 넘어가면 불필요한 반복을 조금이나마 더 줄일 수 있다.

5. 마지막 반복문에서, 합한 값이 딱 m이면 더 계산할 것 없이 m이 최댓값이므로 거기서 반복을 종료하면 된다.

 

코드

fun main() {
    val n = readInt()
    val m = readInt()

    val numbers = IntArray(n)
    for (i in 0 until n) {
        numbers[i] = readInt()
    }

    print(solution(numbers, n, m))
}

private fun solution(numbers: IntArray, n: Int, m: Int): Int {
    var max = 0
    var sum: Int
    for (i in 0 until n - 2) {
        if (numbers[i] > m) continue // 제한보다 크면 다음으로 skip
        for (j in i + 1 until n - 1) {
            if (numbers[i] + numbers[j] > m) continue // 제한보다 크면 다음으로 skip
            for (k in j + 1 until n) {
                sum = numbers[i] + numbers[j] + numbers[k]
                if (sum == m) return sum // 제한과 같으면 바로 반환
                if (sum in (max + 1) until m) max = sum // 제한보다 작으면서 기존 최댓값보다 크면 최댓값 갱신
            }
        }
    }
    return max // 최댓값 반환
}

private fun readInt(): Int {
    var value = 0
    var input: Int
    while (true) {
        input = System.`in`.read() // 한글자 읽기
        when (input) {
            10, 32 -> return value // 공백이나 개행자면 입력을 멈추고 반환
            else -> value = value * 10 + (input - 48) // 기존값에 10을 곱하고 입력값을 숫자로 변환해서 합산
        }
    }
}