[Kotlin, G1] 백준 1300번 K번째 수

출처: unsplash.com

 

K번째 수(1300번)

Gold 1

#이분 탐색 #매개 변수 탐색

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

 

문제 내용

 

 

문제 접근

문제 자체는 이해하는 데 어렵지 않다.

배열의 index는 1부터 시작한다. 각 배열에 들어 있는 수들은 각 index의 곱이다.

그러므로 표로 나타내 보면 아래와 같다.

사진 1-1

위 표에는 5 * 5 크기의 2차원 배열에 들어갈 수들을 나열해 놨다.

각 index의 곱으로 이루어져 있다.

모든 값들은 각 줄에 해당하는 배수들로 이루어져 있는 것을 볼 수 있다.

1번째 줄은 1의 배수, 2번째 줄은 2의 배수 ... 5번째 줄은 5의 배수로 이루어져 있다.

 

입력 예제에서는 3 * 3의 2차원 배열의 값들을 정렬했을 때, 7번째 값을 불러와야 한다.

우선 배열 데이터를 정렬해 보면 1, 2, 2, 3, 3, 4, 6, 6, 9의 순서대로 정렬이 가능하고, 이 중 7번째 수는 첫 번째 6이다.

우리가 찾아야 하는 값이 7번째 값이다. 그리고 B[7] = 6이기 때문에 6보다 작거나 같은 수들이 7개가 존재한다는 뜻이 된다.

정답을 구하기 위해 B[k] = T에서 T의 값을 변경해 가면서 정답을 찾아가야 한다.

 

그러면 T에 맞는 k의 개수를 구하기 위해서는 어떻게 구해야 할까?

먼저 위의 표에서 7보다 작거나 같은 수의 개수를 라인별로 구해 보면 아래와 같다.

사진 1-2

물론 일일이 구하는 방법도 있지만 더 빠르게 구할 수 있는 방법이 있다.

7 / 라인을 해주면 7보다 작거나 같은 수의 개수를 구할 수 있다. 2번째 줄의 개수는 7 / 2에서 소수점을 버린 3이 된다.

하지만 여기서 고려해야 하는 사항이 있다. 바로 나눈 몫이 5보다 커지는 경우이다. 몫이 5보다 커지면 5로 조정을 해주어야 한다.

1번째 줄인 경우에는 7 / 1로 몫이 7이 되는데, 수는 5개까지 있기 때문에 몫이 5보다 커지게 되면 자동으로 5가 될 수 있도록 만들어야 한다.

 

이를 kotlin 코드로 나타내면 다음과 같다.

min(t / i, size)

i번째 줄에서 t보다 작거나 같은 수의 개수를 구한다. 그리고 현재 라인 당 수의 개수를 size로 받고 두 수에서 더 작은 값을 구한다.

그러면 t / i가 size보다 커질 때도 size로 고정된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

private var size: Int = 0
private var index: Int = 0
private var answer = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    size = readLine().toInt()
    index = readLine().toInt()

    binarySearch(1, index)
}

private fun binarySearch(start: Int, end: Int) {
    val mid = (start + end) / 2
    if (start > end) {
        println(answer)
        return
    }

    var cnt = 0
    for (i in 1 .. size) {
        cnt += min(mid / i, size)
    }

    if (cnt < index) binarySearch(mid + 1, end)
    else {
        answer = mid
        binarySearch(start, mid - 1)
    }
}

 

문제 풀이

배열의 크기와 찾아야 하는 index를 입력받고 binary search를 수행한다.

binary search의 mid가 배열 B의 index번째 값의 후보가 된다.

 

반복을 돌려서 mid보다 작거나 같은 수의 총개수를 구해 주고, cnt가 우리가 원하는 정답보다 작으면 mid 값이 더 커야 cnt의 개수를 더 늘릴 수 있다. 정답보다 크거나 같으면 값이 더 작아져야 하기 때문에 mid 값이 더 작아져야 한다.

 

 

문제 해결 과정

오랜만에 풀어보는 이분 탐색 문제였다.

그거와 별개로 그냥 어려웠다. 어떻게 문제를 풀어야 할지 감이 안 잡혔다.

사진 1-1까지는 생각해 봤지만 그 이상의 아이디어가 생각나지 않았다.

그래서 풀이를 참고해서 해결하였다.

포스팅을 작성하면서 문제를 다시 복기해 보니 로직이 이해가 되기 시작했다. 그래서 포스팅 내용이 좀 난잡할 수 있기 때문에 내가 참고한 다른 분들의 풀이 포스팅도 남겨 놓겠다.

 

내가 참고한 문제 풀이 1

BOJ - 1300 k번째 수 해결 전략 (C++)

내가 참고한 풀이 2

[BOJ] 1300 : K번째 수