[백준] 1789번 수들의 합(이분 탐색)[Kotlin - 코틀린]

백준 1789번 문제입니다. (solved.ac) 기준 실버 5 문제입니다.

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

1789번: 수들의 합

문제

자연수 s를 입력받고, 1부터 n까지의 합이 s가 되는 최대 n값을 구하면 되는 문제입니다. 1 ~ n까지의 합을 구하기 위하여 반복문을 사용해도 되지만(O(n)) n이 커질수록 연산의 시간이 오래걸릴 것이라고 생각해서 수식을 이용한 함수를 만들었습니다. ( 1 ~ n 까지의 합 = n * (n+1) / 2)

s의 범위가 굉장히 크기 때문에 n값을 찾기위하여 이분탐색을 진행하였습니다. 
탐색의 시작점(start)은 1, 끝점(end)은 s로 시작하였고 이 둘의 중간점인 mid를 기준으로 이분탐색을 진행했습니다.
1~mid까지의 합(sum(mid)) 이 s보다 작거나 같다면 정답이 될 값(maxOfN)인 "최대 n값"을 갱신하고 start를 mid 보다 1 크게 하고 탐색을 다시하였고 1~mid까지의 합이 s보다 크다면 end를 mid보다 1 작게하고 탐색을 다시 진행하였습니다.

이 과정을 시작점(start)가 끝점(end)보다 클 때까지 반복해준다면 maxOfN에 우리가 원하는 값이 담기게 됩니다.

 

문제 접근

정답 코드

fun main() {

    val s = readln().toLong()

    // 자연수 N의 최댓값
    var maxOfN = 0L
    // 이분탐색의 시작점
    var start = 1L
    // 이분탐색의 끝점.
    var end = s

    // 이분 탐색
    while (start <= end) {
    
        var mid = (start + end) / 2

        if (sum(mid) <= s) {
            maxOfN = mid
            start = mid + 1
        } else {
            end = mid - 1
        }
    }

    println(maxOfN)

}

fun sum(n: Long): Long {
    return n * (n + 1) / 2
}