백준 1174 줄어드는 수 Kotlin (백트래킹)

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

1174번: 줄어드는 수

문제

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

입력

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

백트래킹 문제이다.

구현은 dfs 혹은 bfs로 할 수 있다.

본인은 bfs로 짰는데 나름 깔끔한 것 같다.

우선 줄어드는 수의 최댓값은 9876543210이란 걸 알 수 있다.

이보다 높은 수로는 문제에서 요구하는 줄어드는 수를 만들 수 없다.

따라서 -1이 나오는 경우는 n번째 줄어드는 수가 9876543210 이하의 수에서 나오지 않는 경우를 말한다.

 

N번째 줄어드는 수는 어떻게 구할 수 있을까?

 

우선 일의 자리는 모두 줄어드는 수이기 때문에 0부터 9까지를 큐에 넣는다.

이때 n이 10 이하라면 바로 탐색을 종료하고 답을 출력한다.

 

n이 10 이상이라면 bfs를 돌면 된다.

현재 큐에는 순서대로 0,1,2,3,4,5,6,7,8,9 값이 들어있다.

그럼 bfs의 시작은 0에서 시작하고, 이 숫자들에 대해 다음 값들을 큐에 차곡차곡 넣으면 된다.

여기서 다음 값들은 현재 값의 오른쪽에 숫자를 붙이는 형식으로 진행된다.

0은 스킵하고 현재 값이  1이라고 해보자.

1에 0을 붙이면 10으로 줄어드는 수를 만족하므로 10을 큐에 삽입하고 이는 11번째 줄어드는 수가 된다.

다음 탐색할 값은 2

20

21

위 두 값이 각각 12번 째, 13번째 줄어드는 수이다.

이런 식으로 큐에 들어있던 9까지 bfs를 돌고 10은 스킵, 20도 스킵 21은 0을 붙여서 210

이렇게 하면 n번째 줄어드는 수를 찾자마자 프로그램을 종료할 수 있다. 

 

코드

import java.util.*

const val MAX = 9876543210

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

fun bfs(n: Int): Long {
    var cnt=0

    val q: Queue<Long> = LinkedList()
    for (i in 0 .. 9) {
        q.add(i.toLong())
        cnt++
        if(cnt==n){
            return i.toLong()
        }
    }

    while (q.isNotEmpty()) {
        val cur = q.poll()

        for (i in 0 until cur % 10) {
            val next = cur*10+i
            if(next>MAX) continue
            q.add(next)
            cnt++
            if(cnt==n){
                return next
            }
        }
    }
    return -1
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val n = br.readLine().toInt()

    // solve, output
    write("${bfs(n)}")
    close()
}