[ 백준 2635번 ] 수 이어가기

1. 문제

2635번 - 수 이어가기

 

2. 풀이

수열의 전체 길이를 결정짓는 것은 두 번 째 항으로, 입력받은 첫 번째 수 N 만큼만 순회하면 되는 문제이다.

N의 최대값은 30,000이므로 제한 시간 내에 풀이하는데는 문제 없으며, 가장 긴 수열을 찾았을 때 어차피 O(N)의 시간복잡도이므로 별도의 공간을 추가 할당하기 보다, O(N + 1)로 찾은 수열의 두 번째항을 넘김으로써 한 번 더 순회하며 출력하도록 구현하였다.

 

3. 소스코드

fun main() {
    val n = readln().toInt()
    var maxLength = 1
    var ansIdx = 0

    fun findSequence(prev: Int, next: Int, print: Boolean = false): Int {
        return generateSequence(prev to next) { (a, b) -> b to a - b}
            .map {
                if (print) print("${it.first} ")
                it.second
            }
            .takeWhile { it >= 0 }
            .count() + 1
    }

    (0 .. n).forEach {
        val length = findSequence(n, it)
        if (length > maxLength) {
            maxLength = length
            ansIdx = it
        }
    }

    println(maxLength)
    findSequence(n, ansIdx, true)
}