[백준] 1789번 수들의 합 (Kotlin,코틀린)

문제

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

 

예제 입력 1 

200

예제 출력 1 

19

 

---

 

문제 접근

1. 알고리즘을 지속적으로 공부하면서 쉽게 생각하는 방법에 대해서 추론하는 방법을 조금 깨닫고 있는중?!
2. 간단히 1부터 예제 입력(200)보다 커질때까지 더한 후 그 전 숫자와 전전 숫자를 뺀 후 남는 숫자를 더해주면 가장 많은 횟수로 해당 입력을 구성할 수 있다.
3. 예시로 200 은 1~~18 까지 더하면 171이다 여기서 29만 더해주면 19번을 사용하여 200을 구성하는 것이다.

 

알고리즘

1. 먼저 숫자의 범위가 40억이 넘기 때문에 Int 대신 Long으로 계산식을 구성하였다.
2. 1의 경우에는 1이 출력되는 예외 케이스이기에 따로 처리하였다
3. 입력 값과 더해진 숫자의 값이 같아지는 경우 count를 뺄 필요가 없어지기에 count를 한번 더하여 이를 상쇄했다.
4. 그 외의 경우 break한 후 이전 숫자, 이전전 숫자를 빼고(count-2), 해당 공백을 하나의 숫자로 채우기에(count+1) 마지막에 count-1을 하게 된 것이다.
5. 예시 1..18 = 171  ->  1..20 = 210 (count-2) ->   1..18+29(count+1) = 200 

 

정답 코드

fun main() {
    val input = readln().toLong()
    var sum = 0L
    var i = 1L
    var count = 0
    while (true) {
        if (input == 1L) {
            count = 2
            break
        }
        if (input > sum) {
            sum += i
            i++
            count++
        } else if (input == sum) {
            count++
            break
        } else {
            break
        }
    }
    println(count - 1)
}

난이도: 중하

 

헷갈렸던 부분은 딱히 없었다.