백준 2635 수 이어가기 Kotlin (완전탐색)

문제 출처 : https://www.acmicpc.net/problem/2635

2635번: 수 이어가기

문제

다음과 같은 규칙에 따라 수들을 만들려고 한다.

1. 첫 번째 수로 양의 정수가 주어진다.
2. 두 번째 수는 양의 정수 중에서 하나를 선택한다.
3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

입력

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

출력

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

알고리즘 분류

• 수학
• 브루트포스 알고리즘

풀이

프로젝트와 수업으로 바쁘기도 하고 다시 기본기도 기를 겸 좀 쉬어가자는 뜻으로 가벼운 문제들을 풀고 있다.

완전 탐색 문제이다.

주어진 수가 n이라고 할 때, 두 번째 수의 범위를 1부터 n으로 잡는다.

문제에서 주어진 조건대로  input[curIdx-2] - input[curIdx-1]의 값이 0보다 크다면 input.add(sum)을 하고, 

0보다 작다면 현재 설정한 두 번째 수의 리스트 완성이다.

이 리스트의 길이를 최대 리스트의 길이와 비교하며, 최대 리스트 길이보다 현재 리스트 길이가 더 길다면 이를 갱신해 준다.

 

코드

val br = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()){

    val n = br.readLine().toInt()

    var answer =0
    var answerArr = ArrayList<Int>()
    for(i in 1 .. n){
        var list = ArrayList<Int>()
        list.add(n)
        list.add(i)
        var curIdx=2
        while(true){
            val next = list[curIdx-2]-list[curIdx-1]
            if(next<0) break
            list.add(next)
            curIdx++
        }
        if(answerArr.size < list.size){
            for(i in list.indices){
                if(i < answerArr.size){
                    answerArr[i] = list[i]
                }
                else{
                    answerArr.add(list[i])
                }
            }
        }
    }
    write("${answerArr.size}\n")
    for(num in answerArr){
        write("$num ")
    }
    close()
}