[백준] 2231번 - 분해합 with Kotlin

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */

/* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */

참고 자료

[백준] 2231번 - 분해합 : https://www.acmicpc.net/problem/2231

---

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

---

1. MySolution (1754ms)

import kotlin.math.pow

fun main() {
    val N = readLine()!!
    val digitN = N.map{ it.toString().toInt() }
    var ans = 1000000

    fun digitToNum(tmpDigit:ArrayList<Int>, firstDigit: Int): Int{
        if (digitN.size == 1) return firstDigit
        
        val tmp = ArrayList<Int>(tmpDigit.size)
        for (i in tmpDigit.indices){
            tmp.add(tmpDigit[i] * (10.0.pow(tmpDigit.size-i-1)).toInt())
        }
        return tmp.sum() + (firstDigit * (10.0.pow(tmpDigit.size))).toInt()
    }

    fun calcM(depth: Int, tmpDigit: ArrayList<Int>, firstDigit: Int){
        if (depth == digitN.size - 1){
            val digitSum = tmpDigit.sum() + firstDigit // M의 각자리 숫자 합
            val m = digitToNum(tmpDigit, firstDigit) // M
            val n = m + digitSum
            if (n == N.toInt()) {
                if (ans > m) ans = m
            }
            return
        }
        for (i in 0..9){
            tmpDigit.add(i)
            calcM(depth + 1, tmpDigit, firstDigit)
            tmpDigit.remove(i)
        }
    }

    // digitN 의 개수 -> 자리수
    // 가장 높은 자리수
    for (i in 0..digitN[0]){
        calcM(0, ArrayList<Int>(digitN.size), i)
    }
    if (ans == 1000000) print(0) else print (ans)
}

---

2. BestSolution

fun sol(){
    val num = readLine()!!.toInt()
    for (i in 1..num) { // (1)
        var sum = i
        var check = i
        while (check > 0) { // 각 자리수 더함
            sum += check % 10
            check /= 10
        }
        if (sum == num) { // 생성자 찾은 경우
            println(i)
            return
        }
    }
    println(0)
}

위(1) 부분을 아래와 같이 바꿀 시 탐색 횟수를 더 줄일 수 있다. 

fun bestSol(){
    val numStr = readLine()!!
    val num = numStr.toInt()
    for (i in (num - (numStr.length * 9))..num) {
        var sum = i
        var check = i
        while (check > 0) {
            sum += check % 10
            check /= 10
        }
        if (sum == num) {
            println(i)
            return
        }
    }
    println(0)
}

*수학적 원리는 다음 글을 참고하길 바란다.