[알고리즘] 감소하는 수 (백준 1038번)

1038번: 감소하는 수

 백트랙킹을 이용하는 브루트포스 문제이다.

 나올 수 있는 최대 감소하는 수가 9876543210이다. 그렇기에 나올 수 있는 최대 감소하는 수들의 개수를 계산해보면 총 1023개가 나온다. 즉 백트랙킹으로 1023번만에 풀 수 있기 때문에 매번 모든 경우의 수를 구하여도 시간초과가 절대 나지 않기 때문에 모든 경우의 수를  구하여 정렬한 다음 list[N]을 출력 혹은, 1023보다 같거나 큰 수가 N으로 입력되면 -1을 출력하면 된다.

 

Solution

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

import kotlin.collections.ArrayList
import kotlin.collections.HashMap
import kotlin.math.min

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var N = 0
var list = ArrayList<Long>()

fun solution() {

    N = br.readLine().toInt()

    if(N == 0)
        bw.write("0")
    else
    {
        backTracking(0, 1, 0)
        if(list.size - 1 < N)
        {
            bw.write("-1")
            return
        }
        list.sort()
        bw.write(list[N].toString())

    }
}

fun backTracking(index : Int, t : Long, result: Long)
{
    var result = result
    for(i in index..9)
    {
        result += i * t
        list.add(result)
        backTracking(i + 1, t * 10, result)
        result -= i * t
    }
}





fun main() {
    solution()


    br.close()
    bw.close()
}