[백준] 10448번 유레카 이론(브루트포스 - 완전탐색)[Kotlin - 코틀린]

백준 10448번 문제입니다. (solved.ac) 기준 브론즈 1 문제입니다.

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

10448번: 유레카 이론

문제

문제 접근

어렵지 않은 완전 탐색 문제입니다.

삼각수 Tn은 n(n+1)/2 이라는 공식으로 값을 도출할 수 있고(1 ~ n의 수를 더하는 공식),
k를 입력 받고 이 k가 총 3개의 삼각수(Tn)의 합으로 표현되는지 확인하면 되는 문제입니다. 

기본적인 완전탐색으로 접근하였습니다. k를 입력 받으면 3중 포문을 사용하여 모든 Tn + Tn + Tn( ex) T1 + T2 + T1 등)을 확인해보고 k값과 같다면 1을 출력 그렇지 않다면 0을 출력하도록 구현하였습니다. 

시간 제한은 1초, 1초에 대략적인 연산 횟수는 10^8인 10억 회이며 k의 최대 입력값이 1,000이므로 시간 제한을 통과할 수 있습니다.

최적화를 하기 위하여 k까지의 범위를 탐색하지 않고 Tn에서 최대 n값을 구하여 3중 포문에서 탐색할 때 1부터 최대 n까지만 확인하도록 하였습니다. 

최대 n은 Tn공식을 사용하였을 때 k보다 크거나 같아지는 경우의 n값입니다.

정답 코드

fun main() {

    val testCase = readln().toInt()

    repeat(testCase) {

        val k = readln().toInt()

        var maxN = 0
        var ans = 0

        for (no in 1..k) {
            if (tN(no) >= k) {
                maxN = no
                break
            }
        }

        for (i in 1..maxN) {
            for (j in 1..maxN) {
                for (s in 1..maxN) {
                    if (tN(i) + tN(j) + tN(s) == k) {
                        ans = 1
                    }
                }
            }
        }

        println(ans)
    }

}

fun tN(x: Int) = x * (x + 1) / 2