백준 11561 징검다리 Kotlin (수학, 이분 탐색)

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

11561번: 징검다리

문제

승택이는 강을 건너려 한다.

승택이는 수영을 못하기 때문에, 강에 놓인 징검다리를 밟고 건너갈 것이다.

승택이는 수영은 못하지만 제자리뛰기는 정말 잘한다. 원하는 어느 곳으로든지 점프해서 바로 갈 수가 있다.

승택이는 이제 강의 한쪽 변 앞에 서 있다.

강엔 1번부터 시작해 2번, 3번, ... , N번 징검다리가 차례대로 놓여 있다.

강의 폭이 넓은 탓에 징검다리의 수는 엄청나게 많다.

이 징검다리를 모두 밟고 싶지는 않았던 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만을 밟고 가기로 했다.

물론 강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너기 위해 승택이는 다음과 같은 규칙을 정했다.

1. 첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.
2. 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
3. N번 징검다리는 반드시 밟아야 한다.
4. N번 징검다리를 밟은 후 강 건너로 이동할 땐 점프를 하지 않으므로 위의 규칙이 적용되지 않는다.

승택이가 위의 규칙을 지키며 강을 건널 때, 밟을 수 있는 징검다리의 최대 수는 몇 개일까?

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 정수 한 개로 이루어져 있으며, 징검다리의 총 수 N을 의미한다. (1 ≤ N ≤ 1016)

출력

각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다.

알고리즘 분류

• 수학
• 이분 탐색

풀이

10개의 징검다리를 밟는다고 생각해 보자.

규칙에 의하면 징검다리를 많이 밟기 위해선 무조건 점프의 크기를 무조건 1씩 증가해야 한다.

마지막 징검다리는 거리가 1000이든 10000000이든 그냥 뛰면 그만이다.

다시 10개의 징검다리를 밟기 위해 점프하는 거리는

1+2+3+4+5+6+7+8+9+10 = 55이다.

어디서 많이 봤다.

1부터 n까지의 합!

즉 다음과 같은 풀이가 가능하다.

n이 주어질 때 밟을 수 있는 징검다리의 범위는 1부터 n이다.

1부터 n을 이분 탐색하며(n의 범위가 굉장히 크기 때문에 선형 탐색으로는 시간 초과)

mid = 밟은 징검다리의 개수

mid * (mid+1) / 2 가 n보다 작거나 같다면 answer를 mid로 갱신하고 mid를 늘려서 더 많은 징검다리를 밟을 수 있는지 확인한다.

mid * (mid+1) / 2 가 n보다 크다면 mid만큼의 징검다리를 밟을 수 없다는 뜻이기 때문에 mid를 줄인다.

 

n의 범위가 10^16으로, mid*(mid+1)/2 과정에서 long 범위를 초과할 수 있기 때문에 ULong으로 바꿔준다.

코드

import kotlin.math.sqrt
val br = System.`in`.bufferedReader()
fun getInt() = br.readLine().toInt()

fun check(mid: ULong, n: ULong) = mid * (mid + 1u) / 2u <= n

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

    repeat (getInt()) {
        val n = br.readLine().toULong()
        var s: ULong = 1u
        var e: ULong = (sqrt(n.toDouble())*2).toULong()
        var answer: ULong = 0u
        while (s <= e) {
            val mid = (s + e) / 2u
            if (check(mid, n)) {
                answer = mid
                s = mid + 1u
            } else {
                e = mid - 1u
            }
        }
        write("${answer}\n")
    }
    close()
}