[백준] 2635번 수 이어가기(브루트포스 - 완전탐색)[Kotlin - 코틀린]

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

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

2635번: 수 이어가기

문제

문제 접근

입력값으로 양의 정수가 주어집니다.

첫 번째 수에서양의 정수 중 하나를 선택해서 두 번째 수로 놓습니다.세 번째 수 부터는 앞의 앞의 수에서 앞의 수를 빼서 만들어집니다.

이 과정을 음의 정수가 만들어지기 직전까지 합니다. 음의 정수가 만들어지기 직전의 수까지를 하나의 리스트로 만들어줍니다.
이렇게 만들 수 있는 리스트 중 길이가 가장 긴 리스트를 구하여 해당 크기를 출력하고 다음 줄에 해당 리스트의 요소들을 출력해주면 되는 문제입니다.

 

첫 번째 수인 n의 범위가 30,000이하의 양의 정수 이므로 완전탐색을해도 충분히 제한 시간내에 할 수 있다는 판단을 하여 완전 탐색을 진행하였습니다. n ~ 1까지의 모든 수들을 두 번째 수로 선택한 후 위에서 설명한 과정을 반복합니다! 리스트의 요소가 더 많은 리스트가 나올 때마다 갱신하여 마지막에 가장 긴 리스트가 출력될 수 있도록 하였습니다. 

 

정답 코드

fun main() {

    val firNum = readln().toInt()
    var maxSizeList = mutableListOf<Int>()

    for (no in firNum downTo 1) {

        var curList = mutableListOf<Int>()
        curList.add(firNum)
        curList.add(no)

        // 빼고 남은 수
        var remainNum = firNum - no

        while (true) {
            remainNum = curList[curList.lastIndex - 1] - curList[curList.lastIndex]
            if (remainNum < 0) break
            curList.add(remainNum)
        }

        if (curList.size > maxSizeList.size) maxSizeList = curList

    }

    maxSizeList.forEachIndexed { index, it ->
        if (index == 0) println(maxSizeList.size)
        print("$it ")
    }

}