백준 1300 K번째 수

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

분류: 이분탐색

---

접근방식

풀이 자체는 그냥 이진탐색을 이용하면 돼서 그렇게 어렵지 않지만, 이진탐색으로 접근하기가 어려웠던 문제였습니다.

가장 첫 번쨰 접근은 오름차순으로 정렬했을 때 k번째 수라는 건, B[k] 의 원소보다 작거나 같은 수가 k-1개만큼은 있다는 의미가 됩니다.

그럼 B[k]의 원소가 될 어떤 수를 정하고 이 어떤 수보다 작은 수가 k-1개가 있는지 확인하면 됩니다.

문제는 어떤 수보다 작은 수가 몇 개인지 확인하는 방법입니다.
이 방법만 찾으면 이진탐색으로 어떤 수보다 작은 수의 개수가 k보다 작은지 비교해가며 찾아줄 수 있습니다.

어떤 수를 m이라고 했을 때 이 m보다 작은 수가 몇 개가 있는지는 어떻게 확인할 수 있을까요?

문제 행렬의 원소는 i*j로 되어있는데요, 각 행은 그 행의 배수로 이루어져 있습니다. 
따라서 m을 그 행으로 나눠버리면 그 몫이 m보다 작은 수의 개수가 됩니다.

가령 n = 4, m = 7 일 때 2행을 생각해보면

2행은
2  4  6  8 이고
7보다 작은 수는 2, 4, 6 으로 3개가 있고, 7/2 = 3 이 됩니다.

말로하니까 복잡한데요. 쉽게 생각해서

7에서 3의 배수가 몇 개인지 생각해보면, 

7 = 3 + 3 + 1 이 되니까,
7을 3으로 나눠버린 몫인 2가 7보다 작은 수의 개수가 되는겁니다.

실수하면 안 되는 건 n=5, k = 7 일 때 1행은 최대 5개인데 그냥 7/1로 해버리면 7이 되겠죠?
따라서 n과 m/i 중에서 더 작은 수로 생각해줘야 합니다.

여기까지 이해하셨다면 나머지는 기본적인 이진탐색으로 풀 수 있습니다 :)

추가로 n이 k보다 크다면 1행만 해도 k보다 작거나 같은 수가 최소한 k개는 있게 됩니다.
작아도 n은 대칭 형태를 이루고 있으므로 k개 보다는 많겠죠?
따라서 high의 초기값을 k로 잡아줘도 될 것 같습니다.

 

해결방법

다른 분들에 비해 제 풀이가 유난히 속도가 느린데..

다른 분들 풀이를 참고해서 범위 등을 조금씩 개선했는데도 별로 차이가 없네요..

이유를 잘 모르겠습니다 :(

protocol Readable {
    func readSingleValue() -> String
    func readArray(with separator: Character) -> [String]
}

extension Readable {
    func readSingleValue() -> String {
        return readLine()!
    }
    
    func readSingleValue() -> Int {
        return Int(readLine()!)!
    }
    
    func readArray(with separator: Character) -> [String] {
        return readLine()!.split(separator: " ").map { String($0) }
    }
    
    func readArray(with separator: Character) -> [Int] {
        return readLine()!.split(separator: " ").map { Int(String($0))! }
    }
}

class BOJ1300: Readable {
    
    func input() {
        n = readSingleValue()
        k = readSingleValue()
    }
    
    // MARK: Properties
    
    var n: Int!
    var k: Int!
    
    // MARK: Solution
    
    func solution() {
        input()
        
        var low = 0
        var high = k!
        
        while low <= high {
            let m = (low + high) / 2
            var sum = 0
            for i in 1...n {
                sum += min(m / i, n)
            }
            if sum >= k {
                high = m-1
            } else {
                low = m+1
            }
        }
        print(low)
    }
}

BOJ1300().solution()

 

배운점

어떻게 풀어야하나 감이 안 와서 다른 분들의 풀이를 참고해서 해결했습니다.

이진 탐색 문제인 걸 알고 접근했어도 이해하는 게 쉽지 않았네요...

이것이 사고력인가 봅니다...

그래도 연습으로 기를 수 있다고 믿습니다! 부족한만큼 달려야겠습니다 🔥