[백준 알고리즘/Kotlin] 1789번 수들의 합

 

바로 문제로 들어가기 전에... Int, Long 범위보고 가실게요~

 

1. Int와 Long의 범위

1. Int 범위
크기 : 32 bit
범위 : - 2³¹ ~ 2³¹ -1 (- 2,147,483,648 ~ 2,147,483,647, 약 -21억 ~ 21억)

2. Long 범위
크기 : 64bit
범위 -2⁶³ ~ 2⁶³ - 1 (약 -9경 ~ 9경)

대부분의 코드에서는 Int를 사용해도 충분했기에 Int를 사용했지만,

문제에 주어진 입력 조건을 확인해보니, Long을 사용해야겠습니다.

 

 

2. 최종 코드

n * (n + 1) / 2

연속되는 자연수의 합 공식을 사용하여 풀이했습니다.

 

연속되는 수의 곱을 찾기 위해 루트를 사용했는데요,

루트를 이용하면 두 수의 곱에 가장 가까운 값을 빠르게 찾을 수 있을 것이라고 생각했습니다.

예를 들어, 200이라는 수를 기준으로 생각한다면,

n * (n + 1) / 2 <= 200
n * (n + 1) <= 400
n = Math.sqrt(400) = 20 (400의 제곱근)

while (반복하여 확인)
n = 20, 20 * 21 <= 400 ? false (n--)
n = 19, 19 * 20 <= 400 ? true

따라서 답은 19

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))    
    val s = br.readLine().toLong()

    // 조건식
    // n * (n+1) / 2 <= s인 n
    
    val standard = s * 2
    var n = Math.sqrt(standard.toDouble()).toLong()
    
    while (true) {
        val multiply = n * (n + 1)
        if (multiply <= standard) {
            break
        }
        n--
    }
    
    println(n)
    br.close()
}