Kotlin] 백준 1748번 문제 풀이

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

1748번: 수 이어 쓰기 1

 

 

이 문제는.. 문제가 1억까지 있으며, 메모리가 4MB, 시간이 0.15초로 제한되어 있다는게 문제이다. 따라서

val number = readln().toInt()
val result = 0
for (i in 1 .. number) {
	result += i.toString().length
}
println(result)

 

를 이용하면 틀림없이 메모리나 시간 제한이 걸린다.

(필자는 시간이 아니라 메모리 제한이 걸렸는데, for문에서 생성된 문자열이 garbage collection이 안된건가?)

 

그래서 1억을 일일히 브루트 포스하지 않고, 수학적 규칙성을 간파하여 풀어야한다.

 

규칙성은 다음과 같다.

1~9까지 더할땐 1씩 올라가고, 10~99까지는 2씩, 100~999까지는 3씩 올라간다는 점이다.

즉, 숫자가 두자리 수이면, 1의 자리수의 값을 싹 더하고, 남은 2자리수의 갯수를 구하여 *2를 하면 되고,

세자리수라면 1의 자리수의 총합, 2의 자리수 총합을 싹 더하고 남은 세 자리수의 갯수 * 3을 하면 된다.

 

이를 코드로 표현하면

import java.lang.Math.pow
import kotlin.math.pow
import kotlin.system.measureTimeMillis

fun main(args: Array<String>) {
    question1748()
}

fun question1748() {
    val number = readln().toInt()

    // 결과
    var addNum = 0L

	// 자릿수 도출
    var calNum = number
    var square = 1
    while (calNum / 10 != 0) {
        calNum /= 10
        square++
    }
    
	// 자릿수를 구하고 남은 값을 구한다.
    // ex. 252 -> 100까지의 갯수를 뺀 세 자리수의 152개를 남긴다.
    val leftNum = if(square == 1) {
        (number - 1).toLong()
    } else {
        number - 10.0.pow((square - 1).toDouble()).toLong()
    }

	// 꽉 차있는 자릿수의 합을 구한다
    // 1~9까지는 9
    // 10 ~ 99까지는 180개
    // 100 ~ 999까지는 2700개 이므로, 
    // 자릿수 * 9 * 10 ^ 자릿수 임
    for (i in 1 ..< square) {
        val mustAdd = i * 9 * 10.0.pow((i - 1).toDouble()).toLong()
        addNum += mustAdd
    }

	// 위에서 남아있는 나머지 자릿수의 합을 구함.
    var leftAddNum = (leftNum + 1L) * square
    addNum += leftAddNum

    println(addNum)

}